Google
380 Insert Delete GetRandom O(1)

1. Question

Design a data structure that supports all following operations inaverageO(1)time.
  1. 1.
    insert(val): Inserts an item val to the set if not already present.
  2. 2.
    remove(val): Removes an item val from the set if present.
  3. 3.
    getRandom: Returns a random element from current set of elements. Each element must have the
    same probability of being returned.
Example:
1
// Init an empty set.
2
RandomizedSet randomSet = new RandomizedSet();
3
4
// Inserts 1 to the set. Returns true as 1 was inserted successfully.
5
randomSet.insert(1);
6
7
// Returns false as 2 does not exist in the set.
8
randomSet.remove(2);
9
10
// Inserts 2 to the set, returns true. Set now contains [1,2].
11
randomSet.insert(2);
12
13
// getRandom should return either 1 or 2 randomly.
14
randomSet.getRandom();
15
16
// Removes 1 from the set, returns true. Set now contains [2].
17
randomSet.remove(1);
18
19
// 2 was already in the set, so return false.
20
randomSet.insert(2);
21
22
// Since 2 is the only number in the set, getRandom always return 2.
23
randomSet.getRandom();
Copied!

2. Implementation

(1) Hash Table
1
class RandomizedSet {
2
List<Integer> nums;
3
Map<Integer, Integer> map;
4
Random rand;
5
6
/** Initialize your data structure here. */
7
public RandomizedSet() {
8
nums = new ArrayList<>();
9
map = new HashMap<>();
10
rand = new Random();
11
}
12
13
/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
14
public boolean insert(int val) {
15
if (map.containsKey(val)) {
16
return false;
17
}
18
map.put(val, nums.size());
19
nums.add(val);
20
return true;
21
}
22
23
/** Removes a value from the set. Returns true if the set contained the specified element. */
24
public boolean remove(int val) {
25
if (!map.containsKey(val)) {
26
return false;
27
}
28
int index = map.get(val);
29
if (index < nums.size() - 1) {
30
int lastNum = nums.get(nums.size() - 1);
31
map.put(lastNum, index);
32
nums.set(index, lastNum);
33
}
34
map.remove(val);
35
nums.remove(nums.size() - 1);
36
return true;
37
}
38
39
/** Get a random element from the set. */
40
public int getRandom() {
41
return nums.get(rand.nextInt(nums.size()));
42
}
43
}
44
45
/**
46
* Your RandomizedSet object will be instantiated and called as such:
47
* RandomizedSet obj = new RandomizedSet();
48
* boolean param_1 = obj.insert(val);
49
* boolean param_2 = obj.remove(val);
50
* int param_3 = obj.getRandom();
51
*/
Copied!

3. Time & Space Complexity

时间复杂度: insert: O(1), remove: O(1), getRandom: O(1)
空间复杂度: O(n), n是插入的数的个数