Medium
題目要求是Design a data structure that supports all following operations in average O(1) time.難點(diǎn)在于remove的時(shí)候如何做到average O(1). 這里用HashMap存val - index pair, 用ArrayList存val. remove()的方法是交換要remove的index和最后一個(gè)加入的元素的index，這樣可以做到O(1).

class RandomizedSet {
    Map<Integer, Integer> valIndexMap;
    List<Integer> valList;
    /** Initialize your data structure here. */
    public RandomizedSet() {
        valIndexMap = new HashMap<>();
        valList = new ArrayList<>();
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
        if (valIndexMap.containsKey(val)){
            return false;
        }
        valIndexMap.put(val, valList.size());
        valList.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 (!valIndexMap.containsKey(val)){
            return false;    
        }
        valIndexMap.put(valList.get(valList.size() - 1), valIndexMap.get(val));
        valIndexMap.remove(val);
        valList.remove((Integer) val);
        return true;
    }
    
    /** Get a random element from the set. */
    public int getRandom() {
        Random r = new Random();
        return valList.get(r.nextInt(valList.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();
 */