380. Insert Delete GetRandom O(1)

發表於 | 分類於

problem

solution

利用 array 與 hash table (key:value), key存array元素，value存array索引

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class RandomizedSet {
private:
    // set : insert O(logn), delete O(logn)
    // unordered_set : insert O(1), delete O(1) 分攤後
    // map : insert O(logn), delete O(logn)
    // unordered_map : insert O(1), delete O(1) 分攤後
    
    // 存 value
    vector<int> vec;
    // key 存 list的索引，因為key 必須唯一， value 存value
    // key 存vec的value，value 唯一 , value存索引
    unordered_map<int,int> val2idx;
    
public:
    RandomizedSet() {
        
    }
    
    bool insert(int val) {
        if(val2idx.find(val) !=val2idx.end()) return false;
        val2idx[val] = vec.size();
        vec.push_back(val);
        return true;
    }
    
    bool remove(int val) {
        
        if(val2idx.find(val)==val2idx.end()) return false;
        // 重點，需要從vector移除指定元素，但必須要O(1)
        int idx = val2idx[val];
        val2idx[vec.back()] = idx;
        swap(vec[idx], vec.back());
        // remove the last element, this 
        val2idx.erase(val);
        vec.pop_back();
        return true;
    }
    
    int getRandom() {
        return vec[rand()% vec.size()];
        
    }
};