摘要：思路可以實(shí)現(xiàn)時(shí)間復(fù)雜度的和，但是要求也是，只用是不可以的。但是在里面查找的時(shí)間復(fù)雜度依然是，可以想到用來(lái)記錄對(duì)應(yīng)的，這樣查找的時(shí)間也是常數(shù)。用可以保持順序，但是的時(shí)間復(fù)雜度是。

Design a data structure that supports all following operations in average O(1) time.

insert(val): Inserts an item val to the set if not already present.

remove(val): Removes an item val from the set if present.

getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.

HashSet可以實(shí)現(xiàn)O(1)時(shí)間復(fù)雜度的insert和remove，但是要求getRandom也是O(1)，只用HashSet是不可以的。在List里面隨機(jī)找一個(gè)數(shù)的時(shí)間是O(1)，所以可以用list來(lái)記錄加進(jìn)去的value，這樣insert和getRandom都是O(1)了。remove的操作比較有意思，在一個(gè)list里面找到相應(yīng)的值之后和最后一個(gè)位置上的值調(diào)換，這個(gè)remove就是常數(shù)時(shí)間了。但是在list里面查找的時(shí)間復(fù)雜度依然是O(N)，可以想到用hashmap來(lái)記錄對(duì)應(yīng)的index，這樣查找的時(shí)間也是常數(shù)。

Time: O(1), Space: O(N)

    Map map;
    List list;
    Random random;
    public RandomizedSet() {
        // hashmap to realize insert, remove in O(1), the value is the index in list
        map = new HashMap();
        // list to realize get random in O(1);
        list = new ArrayList();
        random = 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) {
        // change the val with the last one, then delete last one
        if(!map.containsKey(val)) return false;
        int delete_index = map.get(val);
        int last = list.get(list.size() - 1);
        // change the last element to the delete place
        list.set(delete_index, last);
        // update the index in map
        map.replace(last, delete_index);
        // remove in the list
        list.remove((int) list.size() - 1);
        // remove in the map
        map.remove(val);
        return true;
    }
    
    /** Get a random element from the set. */
    public int getRandom() {
        if(list.size() == 0) return -1;
        return list.get(random.nextInt(list.size()));
    }

允許duplication之后麻煩了許多?，F(xiàn)在hashmap里面要存所有的index。在remove的時(shí)候復(fù)雜度要保持O(1)，每次還是要取最后一個(gè)值和刪除的值交換，所以需要map里面找到最后一個(gè)值，之后刪除最大的index的時(shí)間復(fù)雜度是O(1)，同時(shí)把index更新成當(dāng)前刪除的值的index之后，所有的index還要保持順序。

用heap可以保持順序，但是poll的時(shí)間復(fù)雜度是O(logN)。

Map> map;
    List list;
    Random random;
    public RandomizedCollection() {
        map = new HashMap();
        list = new ArrayList();
        random = 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(map.containsKey(val)) {
            map.get(val).add(list.size());
            list.add(val);
            return false;
        }
        else {
            map.put(val, new PriorityQueue<>((a, b) -> b - a));
            map.get(val).add(list.size());
            list.add(val);
            return true;
        }
    }
    
    /** Removes a value from the collection. Returns true if the collection contained the specified element. */
    public boolean remove(int val) {
        if(!map.containsKey(val)) return false;
        int delete_index = map.get(val).peek();
        int last = list.get(list.size() - 1);
        // update
        list.set(delete_index, last);
        map.get(last).poll();
        map.get(last).add(delete_index);
        // delete
        list.remove(list.size() - 1);
        map.get(val).poll();
        if(map.get(val).size() == 0) map.remove(val);
        return true;
    }
    
    /** Get a random element from the collection. */
    public int getRandom() {
        return list.get(random.nextInt(list.size()));
    }