380. Insert Delete GetRandom O(1)

public class RandomizedSet { HashMap<Integer, Integer> map; List list; Random rnd; /* Initialize your data structure here. / public RandomizedSet() { map = new HashMap<Integer, Integer>(); list = new ArrayList(); rnd = new Random(); }

/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
public boolean insert(int val) {
    if(map.containsKey(val))
    return false;
    map.put(val, list.size());
    list.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(!map.containsKey(val))
    return false;
    int index = map.get(val);
    int lastEle = list.get(list.size()-1);//get()参数是key，拿到的事value
    list.set(index, lastEle);
    list.remove(list.size()-1);//每次删除最后一个元素，O（1）时间
    map.put(lastEle, index);
    map.remove(val);
    return true;
}

/** Get a random element from the set. */
public int getRandom() {
    return list.get(rnd.nextInt(list.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(); */

Shawngbk / Leecode

380. Insert Delete GetRandom O(1) #170