常数时间删除/查找数组中的任意元素

实现随机集合

这是力扣第 380 题「 常数时间插入、删除和获取随机元素」，看下题目：

就是让我们实现如下一个类：

class RandomizedSet {
    
public:
    /** 如果 val 不存在集合中，则插入并返回 true，否则直接返回 false */
     bool insert(int val) {
    }
    
    /** 如果 val 在集合中，则删除并返回 true，否则直接返回 false */
    bool remove(int val) {
    }
    
    /** 从集合中等概率地随机获得一个元素 */
    int getRandom() {
    }
}

难度在于2点：

1. 插入，删除，随机获取元素三个操作的时间复杂度都是O（1）
2. getRandom方法返回的元素必须是等概率返回的

我们先来分析一下：对于插入，删除，查找这几个操作，哪种数据结构的时间复杂度是 O(1)？

HashSet 肯定算一个对吧。哈希集合的底层原理就是一个大数组，我们把元素通过哈希函数映射到一个索引上；如果用拉链法解决哈希冲突，那么这个索引可能连着一个链表或者红黑树。

那么请问对于这样一个标准的 HashSet，你能否在 O(1) 的时间内实现 getRandom 函数？

其实是不能的，因为根据刚才说到的底层实现，元素是被哈希函数「分散」到整个数组里面的，更别说还有拉链法等等解决哈希冲突的机制，所以做不到 O(1) 时间「等概率」随机获取元素。

LinkedHashSet 只是给 HashSet 增加了有序性，依然无法按要求实现我们的 getRandom 函数，因为底层用链表结构存储元素的话，是无法在 O(1) 的时间内访问某一个元素的。

根据上面的分析，对于 getRandom 方法，如果想「等概率」且「在 O(1) 的时间」取出元素，一定要满足：底层用数组实现，且数组必须是紧凑的。

所以，如果我们想在 O(1) 的时间删除数组中的某一个元素 val，可以先把这个元素交换到数组的尾部，然后再 pop 掉。

交换两个元素必须通过索引进行交换对吧，那么我们需要一个哈希表 valToIndex 来记录每个元素值对应的索引。

class RandomizedSet {
    
    //<val,index>记录每个元素对应在 nums 中的索引
    private HashMap<Integer,Integer> valToIndex;
    // 存储元素的值
    private List<Integer> list;
    private Random random=new Random();
    public RandomizedSet() {
    
        valToIndex=new HashMap<>();
        list=new ArrayList<>();
    }
    
    public boolean insert(int val) {
    
        // 若 val 已存在，不用再插入
        if (valToIndex.containsKey(val)) return false;
        // 若 val 不存在，插入到 nums 尾部，
        // 并记录 val 对应的索引值
        valToIndex.put(val,list.size());
        list.add(val);
        return true;
    }
    
    public boolean remove(int val) {
    
        // 若 val 不存在，不用再删除
        if(!valToIndex.containsKey(val)) return false;
         // 先拿到 val 的索引
        int removePo=valToIndex.get(val);
        int lastVal=list.get(list.size()-1);
        // 将最后一个元素对应的索引修改为 index
        valToIndex.put(lastVal,removePo);
        // 将位置val设置为最后一个元素
        list.set(removePo,lastVal);
        //删除最后一个位置
        valToIndex.remove(val);
        list.remove(list.size()-1);
        return true;
    }
    
    public int getRandom() {
    
        return list.get(random.nextInt(list.size()));
    }
}

至此，这道题就解决了，每个操作的复杂度都是 O(1)，且随机抽取的元素概率是相等的。

避开黑名单的随机数

有了上面一道题的铺垫，我们来看一道更难一些的题目，力扣第 710 题「 黑名单中的随机数」

题目要求，在 pick 函数中应该尽可能少调用随机数生成函数 rand()。

思路：还是使用map存储黑名单中元素和对应的映射

class Solution {
    
    int size = 0;
    HashMap<Integer, Integer> map = new HashMap<>();
    public Solution(int n, int[] blacklist) {
    
        size = n - blacklist.length;
        //map存放blackList中的元素
        for(int item : blacklist){
    
            map.put(item, -1);
        }

        int last = n - 1;
        for(int item : blacklist){
    
            //若本来就在后面就不动
            if(item >= size){
    
                continue;
            }
            //不然找到最后面不在blacklist中的位置
            while(map.containsKey(last)){
    
                last--;
            }
            //将黑名单元素存在该位置
            map.put(item, last);
            last--;
        }
    }
    
    public int pick() {
    
        int index = (int)(Math.random()*size);
         return map.getOrDefault(index, index);
    }
}