Design a data structure that supports all following operations in average O(1) time.

  1. insert(val): Inserts an item val to the set if not already present.
  2. remove(val): Removes an item val from the set if present.
  3. getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// Init an empty set.
RandomizedSet randomSet = new RandomizedSet();
// Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomSet.insert(1);
// Returns false as 2 does not exist in the set.
randomSet.remove(2);
// Inserts 2 to the set, returns true. Set now contains [1,2].
randomSet.insert(2);
// getRandom should return either 1 or 2 randomly.
randomSet.getRandom();
// Removes 1 from the set, returns true. Set now contains [2].
randomSet.remove(1);
// 2 was already in the set, so return false.
randomSet.insert(2);
// Since 2 is the only number in the set, getRandom always return 2.
randomSet.getRandom();

思路

利用hashtable，访问与删除平均都可以达到O(1)；

利用vector记录，random访问平均是O(1)，在头尾插入删除平均访问时间也是O(1)；

vector在删除的时候，可以只删除最后一个元素，然后把该元素和待删除的元素位置对换即可。这样的时间复杂度也是O(1)。

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class RandomizedSet {
private:
    unordered_map<int, int> map;
    vector<int> values;
public:
    /** Initialize your data structure here. */
    RandomizedSet() {
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    bool insert(int val) {
        if(map.find(val) == map.end()){
            map[val] = values.size();
            values.push_back(val);
            return true;
        }
        else{
            return false;
        }
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    bool remove(int val) {
        if(map.find(val) == map.end()){
            return false;
        }
        else{
            int index = map[val];
            int lastele = values.back();
            if(index == values.size() - 1){
                map.erase(val);
                values.pop_back();
            }
            else{
                map.erase(val);
                map[lastele] = index;
                values[index] = lastele;
                //map.erase(val);
                values.pop_back();
            }
            return true;
        }
    }
    
    /** Get a random element from the set. */
    int getRandom() {
        if(values.size() > 0){
            int index = rand() % values.size();
            int choose = values[index];
            return choose;
        }
        else{
            return -1;
        }
    }
};
/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet obj = new RandomizedSet();
 * bool param_1 = obj.insert(val);
 * bool param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */