class RandomizedSet {
HashSet<Integer> set;
Random rand = new Random();
/** Initialize your data structure here. */
public RandomizedSet() {
set = new HashSet<>();
}
/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
public boolean insert(int val) {
if (set.contains(val)) return false;
set.add(val);
return true;
}
/** Removes a value from the set. Returns true if the set contained the specified element. */
public boolean remove(int val) {
if (set.contains(val)) {
set.remove(val);
return true;
}
return false;
}
/** Get a random element from the set. */
public int getRandom() {
int size = set.size();
int idx = rand.nextInt(size);
Iterator<Integer> iter = set.iterator();
for (int i = 0; i < idx; i++) {
iter.next();
}
return iter.next();
}
}
/**
* Your RandomizedSet object will be instantiated and called as such:
* RandomizedSet obj = new RandomizedSet();
* boolean param_1 = obj.insert(val);
* boolean param_2 = obj.remove(val);
* int param_3 = obj.getRandom();
*/
HashMap and ArrayList:
class RandomizedSet {
HashMap<Integer, Integer> hash;
ArrayList<Integer> list;
int size;
/** Initialize your data structure here. */
public RandomizedSet() {
hash = new HashMap<>();
list = new ArrayList<>();
size = 0;
}
/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
public boolean insert(int val) {
if (hash.containsKey(val)) return false;
hash.put(val, size);
list.add(val);
size++;
return true;
}
/** Removes a value from the set. Returns true if the set contained the specified element. */
public boolean remove(int val) {
if (!hash.containsKey(val)) return false;
int lastIndex = size - 1;
int index = hash.get(val);
if (index < lastIndex) {
int lastVal = list.get(lastIndex);
list.set(index, lastVal);
hash.put(lastVal, index);
}
hash.remove(val);
list.remove(lastIndex);
size--;
return true;
}
/** Get a random element from the set. */
public int getRandom() {
return list.get(new Random().nextInt(size));
}
}
/**
* Your RandomizedSet object will be instantiated and called as such:
* RandomizedSet obj = new RandomizedSet();
* boolean param_1 = obj.insert(val);
* boolean param_2 = obj.remove(val);
* int param_3 = obj.getRandom();
*/
Using HashSet, runtime beats 16%:
HashMap and ArrayList: