2022-04-13 约 600 字预计阅读 2 分钟 - 次阅读

Leetcode 380: O(1)时间插入、删除和获取随机元素

22年4月13日每日一题

初始想法

最简单的想法是数组，但是数组的插入和删除并不是O(1)的。如果使用哈希表的话，插入和删除是O(1)的，但是随机化并不是O(1)。

因此，只需要将数组和哈希表结合起来，使用哈希表进行插入和删除，并使用数组来进行随机化。问题在于数组中的元素删除代价不一定是O(1)，这个可以使用最后元素的置换来完成。

#include <iostream>
#include <vector>
#include <map>
#include <ctime>
using namespace std;

class RandomizedSet {
public:
    map<int,int> store;
    vector<int> q;
    RandomizedSet() {
        store.clear();
        q.clear();
    }
    
    bool insert(int val) {
        if(store.find(val)==store.end()){
            q.emplace_back(val);
            store[val] = q.size()-1;
            return true;
        }

        return false;
    }
    
    bool remove(int val) {
        if(store.find(val)==store.end()){
            return false;
        }

        int cur_pos = store[val];
        int last_pos = q.size()-1;
        if(cur_pos != last_pos){ // 将要删除的元素换到最末尾
            int last_val = q[last_pos];
            q[cur_pos] = last_val;
            store[last_val] = cur_pos;
        }
        q.pop_back();
        store.erase(val);
        return true;
    }
    
    int getRandom() {
        int num = rand()%q.size();
        return q[num];
    }
};



int main(void){
    RandomizedSet s;
    s.insert(1);
    s.insert(2);
    s.insert(3);
    s.insert(4);
    cout<<s.getRandom()<<endl;

    return 0;
}

执行用时：256 ms, 在所有 C++ 提交中击败了5.50%的用户内存消耗：95 MB, 在所有 C++ 提交中击败了5.42%的用户

通过测试用例： 19 / 19

最终结果比较一般。

改进

官方的做法比较一致，但是使用unorder_map代替map，因为map是用红黑树做的，unordered_map是用哈希表做的，因此两者操作上具有差距。

class RandomizedSet {
public:
    RandomizedSet() {
        srand((unsigned)time(NULL));
    }
    
    bool insert(int val) {
        if (indices.count(val)) {
            return false;
        }
        int index = nums.size();
        nums.emplace_back(val);
        indices[val] = index;
        return true;
    }
    
    bool remove(int val) {
        if (!indices.count(val)) {
            return false;
        }
        int index = indices[val];
        int last = nums.back();
        nums[index] = last;
        indices[last] = index;
        nums.pop_back();
        indices.erase(val);
        return true;
    }
    
    int getRandom() {
        int randomIndex = rand()%nums.size();
        return nums[randomIndex];
    }
private:
    vector<int> nums;
    unordered_map<int, int> indices;
};