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

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

思路

哈希表可以完成$O(1)$的插入和删除，但是无法用下标获得元素。考虑到变长数组可以在$O(1)$的时间完成获取元素，我们只需要再维护一个变长数组即可。用哈希表维护元素即它们在变长数组的位置。在添加元素时，把元素添加到变长数组的末端；在删除元素时，更新数组末端元素在哈下表的位置，用末端元素替换数组被删除元素。

复杂度

• 时间复杂度: $O(1)$，哈希表插入删除时间都是$O(1)$，删除数组最后一个元素也是$O(1)$。
• 空间复杂度: $O(n)$，哈希表和数组。

Code

[]

class RandomizedSet {
    private Map<Integer, Integer> s;
    private List<Integer> a;
    private int count;
    private Random random;
    
    public RandomizedSet() {
        s = new HashMap<>();
        a = new ArrayList<>();
        random = new Random();
        count = 0;
    }

    public boolean insert(int val) {
        if (s.containsKey(val)) return false;
        s.put(val, count);
        a.add(val);
        count++;
        return true;
    }

    public boolean remove(int val) {
        if (!s.containsKey(val)) return false;
        count--;
        s.put(a.get(count), s.get(val));
        a.set(s.get(val), a.get(count));
        a.remove(count);
        s.remove(val);
        return true;
    }

    public int getRandom() {
        return a.get(random.nextInt(count));
    }
}