380 Insert Delete GetRandom O(1)

380. Insert Delete GetRandom O(1)​
1. Question
Design a data structure that supports all following operations inaverageO(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
// 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是插入的数的个数

481 Magical String

800 Similar RGB Color

Last modified 2yr ago

Copy link

Contents

380. Insert Delete GetRandom O(1)

1. Question

2. Implementation

3. Time & Space Complexity

380. Insert Delete GetRandom O(1)​

1. Question

2. Implementation

3. Time & Space Complexity

380. Insert Delete GetRandom O(1)