380.O(1)时间插入、删除和获取随机元素

哈希表

题目要求插入、删除、随机删除复杂度均为$O(1)$，其中需要判断元素是否在集合中，所以查询特定值的复杂度也需要达到$O(1)$，常见数据结构中：

数据结构	插入复杂度	删除复杂度	查询特定值	随机查找
数组	末尾$O(1)$，中间与首部$O(n)$	末尾$O(1)$，中间与首部$O(n)$	$O(n)$	支持
列表	$O(1)$	在已经找到节点的情况下为$O(1)$	$O(n)$	不支持
哈希表	$O(1)$	$O(1)$	$O(1)$	不支持

没有任何一种可以直接满足要求，所以需要组合使用。

此处选取的思路为底层用数组存储数据，支持随机查找需求，插入直接向末尾插入以实现$O(1)$复杂度，删除时交换到数组末尾来达到$O(1)$需求，哈希表采用val-index映射负责维护查询特定值所需的$O(1)$复杂度。

实现中下面的代码给数组预分配了内存并维护指向第一个可用位置的tail指针，这部分可以使用ArrayList代替。

时间复杂度：所有函数均为$O(1)$

空间复杂度：$O(n)$，$n$ 为最大元素数量

class RandomizedSet {
    private Map<Integer, Integer> map = new HashMap<>();
    private int[] cnt = new int[200001];
    private int tail = 0;
    private Random random = new Random();
    public RandomizedSet() {

    }
    
    public boolean insert(int val) {
        if (map.containsKey(val)) {
            return false;
        }
        map.put(val, tail);
        cnt[tail++] = val;
        return true;
    }
    
    public boolean remove(int val) {
        if (!map.containsKey(val)) {
            return false;
        }
        int idx = map.get(val);
        if (idx != tail - 1) {
            swap(cnt, idx, tail - 1);  // 交换到数组末尾
            map.put(cnt[idx], idx);  // 末尾元素索引更新
        }
        map.remove(val);
        tail--;
        return true;
    }
    
    public int getRandom() {
        return cnt[random.nextInt(tail)];
    }

    private void swap (int[] a, int l, int r) {
        int tmp = a[l];
        a[l] = a[r];
        a[r] = tmp;
    }
}

/**
 * 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();
 */