## Leetcode 381. o (1) time insert, delete, and get random elements - allow duplicate Java

Princess SINB 2020-11-13 05:15:03
leetcode time insert delete random

Design a support in average Time complexity O(1) Next , Data structure to do the following .

Be careful : Allow duplicate elements .

insert(val)： Insert element into collection val.
remove(val)： When val In existence , Remove one from the collection val.
getRandom： Get an element at random from an existing collection . The probability of each element being returned should be linearly related to its number in the set .

`````` Example :
// Initialize an empty collection .
RandomizedCollection collection = new RandomizedCollection();
// Insert into collection 1 . return true Indicates that the collection does not contain 1 .
collection.insert(1);
// Insert another into the collection 1 . return false Indicates that the collection contains 1 . The collection now contains [1,1] .
collection.insert(1);
// Insert into collection 2 , return true . The collection now contains [1,1,2] .
collection.insert(2);
// getRandom Ought to have 2/3 Probability return of 1 ,1/3 Probability return of 2 .
collection.getRandom();
// Remove from collection 1 , return true . The collection now contains [1,2] .
collection.remove(1);
// getRandom There should be the same probability of return 1 and 2 .
collection.getRandom();
source ： Power button （LeetCode）
``````
``````class RandomizedCollection {

List<Integer> list;
Random r;
/** Initialize your data structure here. */
public RandomizedCollection() {

list=new ArrayList<>();
r=new Random();
}
/** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
public boolean insert(int val) {

if(list.contains(val)){

return false;
}
else {

return true;
}
}
/** Removes a value from the collection. Returns true if the collection contained the specified element. */
public boolean remove(int val) {

for(int i=0;i<list.size();i++){

if(list.get(i)==val){

list.remove(i);
return true;
}
}
return false;
}
/** Get a random element from the collection. */
public int getRandom() {

int index=r.nextInt(list.size());
return list.get(index);
}
}
/**
* Your RandomizedCollection object will be instantiated and called as such:
* RandomizedCollection obj = new RandomizedCollection();
* boolean param_1 = obj.insert(val);
* boolean param_2 = obj.remove(val);
* int param_3 = obj.getRandom();
*/
``````