经过昨天的消沉

今天我振作了

设计个数据结构，添加，删除，随机获取都是O(1).

怎么会有这么牛逼的数据结构，所以肯定相应的要耗费空间。

添加和获取耗时O(1)是Array的特性，或者说是Map/Table的特性，思考下php的array就明白其实是index的mapping了。

Random要求O(1)那就是需要知道数据结构的大小，并且保证储存的元素是相邻的。

其实就是一个table/map，KEY是添加的元素，value是他储存在array中的位置；

然后一个array和上面的table/map对应；

再一个变量size记录总共有多少个元素，便于random.

添加，直接添加到SIZE的位置，MAP里记录，SIZE++

RANDOM，通过SIZE随便RANDOM一个数，直接从ARRAY里直接获取。

删除，为了保证所有元素在ARRAY中是相邻的，像LIST那样。用ARRAY模拟就是删除之后，后面所有的都前移，但是要求O(1)，可以把最后一个元素和它换一下。换的时候相应的改变MAP/TABLE里的信息，删除map里本来最后一个KEY（因为我们换到前面了），最后SIZE--，使得array[size]指向的位置虽然不为空，但是是标记为删除的元素，就是刚才换过来的，而RANDOM不会影响。

感觉和学习哦啊以前做过的用JAVA实现PHP ARRAY的作业有点像，只不过那个要自己写hash function

为了图省事不resize array，用了arrayList，但是意思是那个意思。。

public class RandomizedSet {    Map
    
      map;    List
     
       list;    int size;    /** Initialize your data structure here. */    public RandomizedSet()     {        map = new HashMap
      
       ();        list = new ArrayList
       
        ();        this.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;        else        {            list.add(size,val);            map.put(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(!map.containsKey(val)) return false;        else if(size == 0) map.remove(val);        else        {            int tailKey = list.get(size-1);            map.put(tailKey,map.get(val));            list.set(map.get(val),tailKey);            size--;            map.remove(val);                      }        return true;     }        /** Get a random element from the set. */    public int getRandom()     {        Random rdm = new Random();        return list.get(rdm.nextInt(size));    }}
       
      
     
    

---

二刷。

用个Map，KEY是存的元素，VAL是元素存在arraylist里的位置。

删除是把arraylist里最后一个有效元素和删除的元素调换，同时修改map里被最后一个有效元素（key)的相应位置（value）。。

public class RandomizedSet {        List
    
      list;    int num;    Map
     
       map;        /** Initialize your data structure here. */    public RandomizedSet() {        list = new ArrayList<>();        num = 0;        map = new HashMap<>();    }        /** 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;        } else {            list.add(num, val);            map.put(val, num++);            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;        } else if (num == 0) {            map.remove(val);            return true;        } else {            int removedIndex = map.get(val);            int backElement = list.get(num - 1);            map.put(backElement, removedIndex);            list.set(removedIndex, backElement);            num--;            map.remove(val);            return true;        }                }        /** Get a random element from the set. */    public int getRandom() {        Random rdm = new Random();        return list.get(rdm.nextInt(num));    }}