LeetCode:常数时间插入删除获取元素

380. 常数时间插入、删除和获取随机元素

设计一个支持在*平均 *时间复杂度 O(1) 下，执行以下操作的数据结构。

1. insert(val)：当元素 val 不存在时，向集合中插入该项。
2. remove(val)：元素 val 存在时，从集合中移除该项。
3. getRandom：随机返回现有集合中的一项。每个元素应该有相同的概率被返回。

思路：

构建两个map，第一个map存储<val，index>，index为val进入map的的顺序，可根据val查找index；第二个map存储<index，val>正好和第一个反过来，可根据index查找val。还需要维护一个size，表示当前有几个元素。
插入：先判断能否插入，若能则两个map均插入，同时size+1；
获取：返回第二个map的一个随机索引；
删除：先判断第一个map是否存在待删除元素，若存在，则根据第一个map获取待删除val的index，并将该index赋值给第一个map的最后一个元素，并将该元素赋值给第二个map对应的index，最后将第一个map对应的val条目删除，将第二个map的最后一个index删除，并将size-1。这种操作保证了index的连续性，获取随机元素时能保证取得到。

c++语言细节：

两个map要做为类的数据成员，不能声明在某个函数中；
map.find(K)，如果map中存在K，则返回指向该元素得迭代器，若不存在，则返回end()尾后迭代器；
可以通过map[k]=val，进行赋值；
map.erase(it)，是接收迭代器参数的；
c++没有生成0-1的随机数发生器，可以通过rand()%n，来获取0~n-1之间的整数；

class RandomizedSet {
public:
    map<int, int> kindex; // 第一个map k index
    map<int, int> indexK; // 第二个map index K
    int size; //元素个数
    /** Initialize your data structure here. */
    RandomizedSet() {

        size = 0;
    }

    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    bool insert(int val) {
        auto it = kindex.find(val);
        if (it == kindex.end()) //说明该元素不存在，可以插入
        {
            kindex[val] = size;
            indexK[size++] = val;
            return true;
        }
        else
            return false;
    }

    /** Removes a value from the set. Returns true if the set contained the specified element. */
    bool remove(int val) {
        auto it = kindex.find(val);
        if (it != kindex.end()) //说明map中有该元素，可以删除
        {
            int index = kindex[val];  //获取该元素对应的index
            int lastIndex = --size;  // 获取最后一个元素的index
            int lastK = indexK[lastIndex];  //获取最后一个元素的值
            indexK[index] = lastK;  //将待删除元素对应的index的值改忘最后一个元素的值
            kindex[lastK] = index; //将最后一个元素的index改为待删除元素的index
            indexK.erase(lastIndex);//删除最后一个元素的原索引
            kindex.erase(val); //删除待删除元素的值
            return true;
        }
        else
            return false;
    }

    /** Get a random element from the set. */
    int getRandom() {
        if (size == 0) //没有元素了，返回0
            return 0;

        int index = rand() % size; //返回0~size-1
        return indexK[index];
    }
};
/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet* obj = new RandomizedSet();
 * bool param_1 = obj->insert(val);
 * bool param_2 = obj->remove(val);
 * int param_3 = obj->getRandom();
 */