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

难度: 🌕🌗

问题描述

---

解法

class RandomizedSet {
    // 思路：
    // 插入、删除、判断是否存在均可以通过 HashSet 得到 O(1) 复杂度
    // 关键在于，如何随机获取元素，要想随机获取元素，需要通过数组实现，通过数组元素个数得到随机下标，然后删除该下标元素即可
    // 因此，需要同时 借助 Hash & 变长数组 List 实现
    // 在删除 Hash 元素时，复杂度 O(1) 可以达到，如何保证变长数组中删除某下标元素复杂度也为 O(1)?
    // LinkedList 删除特定下标元素，定位到该元素复杂度为 O(N)，因此不可采用
    // ArrayList 若直接删除特定下标元素，支持 O(1) 定位到删除元素，但删除后，后面的元素需要前移，因此需要进行适当转换
    // 即，将该删除下标元素和末尾下标元素互换，然后删除末尾下标元素，这样末尾无元素需要前移，复杂度就降为 O(1)
    HashMap<Integer, Integer> map;
    ArrayList<Integer> list;

    public RandomizedSet() {
        map = new HashMap<>();
        list = new ArrayList<>();
    }
    
    public boolean insert(int val) {
        if(map.containsKey(val)) {
            return false;
        }
        list.add(val);
        int size = list.size();
        map.put(val, size - 1);
        return true;
    }
    
    public boolean remove(int val) {
        if(!map.containsKey(val)) {
            return false;
        }
        int index = map.get(val);
        int size = list.size();
        int last = list.get(size - 1);
        list.set(index, last);
        list.remove(size - 1);
        map.put(last, index); // 需要修改原本最后一个元素所在下标
        map.remove(val);
        return true;
    }
    
    public int getRandom() {
        int size = list.size();
        int rand = new Random().nextInt(size); // [0, size)
        return list.get(rand);
    }
}

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

---

输出