380. O(1) 時間插入，刪除，和獲取隨機元素

思路

只要在每次刪除時，都將要刪除的數字挪到最後一個位置，在取得隨機元素時就不必煩惱中間有空洞該怎麼處理。

• 用一個哈希表紀錄數字對應到的位置，方便跟最後一個數字做交換。
• 在做任何操作之後，都要實時的更新哈希表。

程式碼

哈希表

class RandomizedSet {
private:
    vector<int> nums; // 紀錄當前數字
    unordered_map<int, int> umap; // 紀錄數字對應的位置
public:
    RandomizedSet() {
        srand(time(NULL));
    }
    
    bool insert(int val) {
        if(umap.find(val) == umap.end()) {
            umap[val] = nums.size();
            nums.push_back(val);
            return true;
        }
        return false;
    }
    
    bool remove(int val) {
        if(umap.find(val) != umap.end()) {
            umap[nums.back()] = umap[val];
            swap(nums[umap[val]], nums.back()); // 將要被刪除的數字跟最後一個數字交換，然後丟掉它
            umap.erase(val);
            nums.pop_back();
            return true;
        }
        return false;
    }
    
    int getRandom() {
        int index = rand() % nums.size();
        return nums[index];
    }
};

複雜度分析

• 時間複雜度：$O(1)$
• 空間複雜度：$O(n)$