设计一个数据结构，插入，删除，随机获取其中一个数值操作都是O(1)的时间复杂度。
思考：首先从基本的数据结构开始思考，数组、链表、hash表，map，set等等，发现单一的数据结构是无法支持那些操作都是O(1)的时间复杂度。进而再考虑叠加数据结构的方法。vector + unordered_map 是 不错的叠加方法，用数组存放具体数据，用hash表存放数据的索引。之后再查找时，可以通过索引，再在数组中找到元素。插入时，在vector中插入数据，同时把索引存放到hash里面。插入操作需要注意的是，如果数组本身有对象(v[i] = value)可以直接存放就直接存放，如果没有，在创建对象插入（push_back）.删除时，从hash中找到索引，再在vector中删除，删除时考虑到效率问题，可以直接将最后一个元素搬移到需要删除的位置，并更新vector最后可再插入元素位置。
解法：
class RandomizedSet { public: /** Initialize your data structure here. */ RandomizedSet() { len = 0; } /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */ bool insert(int val) { // 这里一定要判断不能等于-1，因为数组只有一个元素时，对它做删除后，该元素位置会更新为-1 if (idx.count(val) > 0 && data[idx[val]] != -1) { return false; } // 注意这里要比较当前使用的大小和vector的实际大小 if (len == data.size()) { data.push_back(val); } else { data[len] = val; } idx[val] = len++; return true; } /** Removes a value from the set. Returns true if the set contained the specified element. */ bool remove(int val) { if (idx.count(val) == 0) { return false; } int pos = idx[val]; // 把最后一个元素挪到要删除位置，而不是后面的元素整体向前移动，是为了性能考虑 data[pos] = data[--len]; // 之后把最后位置的数据改为-1，表示这里没有数据 data[len] = -1; // 这个不能忘记删除元素 idx.erase(val); idx[data[pos]] = pos; return true; } /** Get a random element from the set. */ int getRandom() { // 不要忘记len是0的情况 if (len == 0) { return -1; } int pos = rand() % len; return data[pos]; } public: // 值和索引的映射关系 unordered_map<int, int> idx; // 具体存放数据 vector<int> data; int len; };
