leetcode 380. Insert Delete GetRandom O(1)

380. Insert Delete GetRandom O(1)

实现插入、删除、获得随机数功能，且时间复杂度都在O(1)。实际上在插入、删除两个功能中都包含了查找功能，当然查找也必须是O(1)。

数组可以实现插入、删除、获得随机数O(1)，但查找就不行了。(当然对于数组，直接删除的时间复杂度不是O(1)，因为可能需要移动)

hash、set都是红黑树实现的，查找、插入、删除的时间复杂度在O(logn)。

unordered_map、unordered_set是哈希表实现的，查找、插入、删除的时间复杂度在O(1)。但unordered_map、unordered_set都只能用迭代器访问，无法用索引访问，所以获得随机数的时间复杂度不是O(1)。但是unordered_map、unordered_set都还是有size()的函数，只是不像vector那样用size来获得index访问。

unordered_set用迭代器访问的方式如下：

#include <iostream>
#include <unordered_set>


using namespace std;

int main(){
    unordered_set<int> s;
    s.insert(10);
    s.insert(11);
    s.insert(12);
    for(auto it = s.begin();it != s.end();it++)
        cout << *it << endl;
}

leetcode 380. Insert Delete GetRandom O(1)

原文：https://www.cnblogs.com/ymjyqsx/p/10882501.html