哈希表：插入、删除、随机访问时间复杂度都为O(1)_哈希表插入删除时间复杂度

题目

https://leetcode-cn.com/problems/FortPu/

解题思路

看到时间复杂度O(1)就可以联想到数组或者哈希表。
这里情况特殊需要考虑getRandom函数，且返回一个相同概率的随机数。所以要实现这个目标，只能从数组里面返回，且数组具有索引。

那么这个题目我们可以设计成的数据结构是：
哈希表： 要修改的元素作为key，而元素的索引作为value。
数组：用来保存元素，且数组索引可以用来生成一个随机数，可以返回一个以随机数作为数组下标的数。

如何从数组中用时间复杂度O（1）来删除一个元素？

这里最容易出错的地方是删除一个数。
数组中删除一个数，需要把数组遍历一次，才能找到被删除的数，这样时间复杂度是O(n); 所以我们得用一个其他技巧：
每次首先把列表最后一个数和要删除的数（其下标我们已经用哈希表作为value存好）交换。交换后，每次固定删除列表最后一个数即可，这样时间复杂度达到O(1);

具体代码如下：

代码

class RandomizedSet {

    //哈希表能实现删除，查询O（1）时间复杂度。
    Map<Integer, Integer> numToLocation = null;

    //想要生成一个相同概率的随机数，则需要列表索引，而哈希表不具有索引，我们得借助数组来完成。
    //Nums里面保存值。 而HashMap的值保存索引。
    ArrayList<Integer> nums = null;
    /** Initialize your data structure here. */
    public RandomizedSet() {
        numToLocation = new HashMap<>();
        nums = new ArrayList<>();
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
        if(numToLocation.containsKey(val)){
            return false;
        }

        numToLocation.put(val, nums.size());
        nums.add(val);
        return true;
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        if(!numToLocation.containsKey(val)) {
            return false;
        }
        int location = numToLocation.get(val);
        numToLocation.put(nums.get(nums.size() - 1), location);
        numToLocation.remove(val);
        nums.set(location, nums.get(nums.size() - 1));
        nums.remove(nums.size() - 1);
        return true;
    }
    
    /** Get a random element from the set. */
    public int getRandom() {
       Random random = new Random();
       int key = random.nextInt(nums.size());
       return nums.get(key);
    }
}

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet obj = new RandomizedSet();
 * boolean param_1 = obj.insert(val);
 * boolean param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */
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

总结

本题考察哈希表和数组的性质，时间复杂度O（1）。同时如何结合哈希表来删除数组一个数，且时间复杂度O（1）。