[leetcode] 380. Insert Delete GetRandom O(1)

[leetcode] 380. Insert Delete GetRandom O(1)
https://leetcode.com/problems/insert-delete-getrandom-o1/description/

看见题第一反应，用hashSet啊，hashtable都不用，直接set。但是忘了考虑一点，hashSet添加和删除都是O（1），但是拿随机的item是O（n）。我用hashSet做了一遍，也AC了但是是错的！！！是错的！！！
这个是错的！！：重要的事情说三遍

public class RandomizedSet {

    HashSet<Integer> set = new HashSet<Integer>();
    /** Initialize your data structure here. */
    public RandomizedSet() {
        
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
        return set.add(val);
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        return set.remove(val);
    }
    
    /** Get a random element from the set. */
    public int getRandom() {
        int size = set.size();
        Random rand = new Random();
        int index = rand.nextInt(size);
        Iterator iterator = set.iterator();
        int i = 0;
        for(Object obj : set){
            if(i == index){
                return (int)obj;
            }
            i++;
        }
        return 0;
    }
}

/**
 * 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();
 */

上面的是错的啊！最后那个return 0是为了通过编译加上去的的，所有东西都在for loop里return了，根本泡不到左后的return 0. 但是这个是错误的示范，很明显，这个getRandom是n的复杂度。

这道题让我们在常数时间范围内实现插入删除和获得随机数操作，如果这道题没有常数时间的限制，那么将会是一道非常简单的题，我们直接用一个set就可以搞定所有的操作。但是由于时间的限制，我们无法在常数时间内实现获取随机数，所以只能另辟蹊径。此题的正确解法是利用到了一个一维数组和一个哈希表，其中数组用来保存数字，哈希表用来建立每个数字和其在数组中的位置之间的映射，对于插入操作，我们先看这个数字是否已经在哈希表中存在，如果存在的话直接返回false，不存在的话，我们将其插入到数组的末尾，然后建立数字和其位置的映射。插入是常数的复杂度这样。删除操作是比较tricky的，我们还是要先判断其是否在哈希表里，如果没有，直接返回false。由于哈希表的删除是常数时间的，而数组并不是，为了使数组删除也能常数级，我们实际上将要删除的数字和数组的最后一个数字调换个位置，然后修改对应的哈希表中的值，这样我们只需要删除数组的最后一个元素即可，保证了常数时间内的删除。而返回随机数对于数组来说就很简单了，我们只要随机生成一个位置，返回该位置上的数字即可。

简言之，set的添加和删除是常数的，random线性、而array的添加和random是常数的，delete线性。所以，这道题要充分利用两个人的有点，合并他们，用在一个data structure中。
AC Solution：

public class RandomizedSet {
   Map<Integer, Integer> map;
    List<Integer> list;
    int size;
    /** Initialize your data structure here. */
    public RandomizedSet() {
        map = new HashMap<Integer, Integer>();
        list = new ArrayList<Integer>();
        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(map.containsKey(val)){
            return false;
        }
        map.put(val, size);
        list.add(size, val);
        size++;
        //System.out.println("Add size: " + size);
        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);
        //map.remove(val); //Wrong
        int tail = list.get(size - 1);
        list.set(index, tail);
        map.put(tail, index);// update the existing ones
        map.remove(val); //Right
        list.remove(size - 1);
        size--;          
        
        //System.out.println("Delete size: " + size);
        return true;
    }
    
    /** Get a random element from the set. */
    public int getRandom() {
        Random rand = new Random();
        //System.out.println("Random size: " + size);
        int i = rand.nextInt(size);
        return (int)list.get(i);
    }
}

/**
 * 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();
 */

有一点百思不得其解倒是，就是remove（val），这个东西放在稍微靠前一点就不对了。只有放在这个位置才对，我标了Wrong，为啥放那就不对了呢？错误：Line 46: java.lang.IllegalArgumentException: bound must be positive
["RandomizedSet","insert","remove","insert","remove","getRandom","getRandom","getRandom","getRandom","getRandom","getRandom","getRandom","getRandom","getRandom","getRandom"] [[],[0],[0],[-1],[0],[],[],[],[],[],[],[],[],[],[]]

rand.nextInt错了，size不能等于0.但是不懂啊，为啥remove的位置一换就错了呢？还是说他的testcase有啥问题啊。

我这猪脑子，想了好久，println了一大堆，终于明白了，我在remove之后又插进去了一遍，也就是互换位置的时候，但是当里面只有一个元素的时候，再插进去就不对了，如果remove在后面，就可以去除那个没用的加进去的元素。 remove放在前面，remove里第一个判断if就进不去，应为那个val一直在的！啊！想了好久，看来我debug的能力没有自己想象的好啊。