O(1)插入、删除和随机元素[中等]

优质博文：IT-BLOG-CN

一、题目

实现RandomizedSet类：
【1】RandomizedSet()初始化RandomizedSet对象。
【2】bool insert(int val)当元素val不存在时，向集合中插入该项，并返回true；否则，返回false。
【3】bool remove(int val)当元素val存在时，从集合中移除该项，并返回true；否则，返回false。
【4】int getRandom()随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。

你必须实现类的所有函数，并满足每个函数的平均时间复杂度为O(1)。

示例：
输入: ["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"] ：[[], [1], [2], [2], [], [1], [2], []]
输出：[null, true, false, true, 2, true, false, 2]

解释：

RandomizedSet randomizedSet = new RandomizedSet();  
randomizedSet.insert(1); // 向集合中插入 1 。返回 true 表示 1 被成功地插入。  
randomizedSet.remove(2); // 返回 false ，表示集合中不存在 2 。  
randomizedSet.insert(2); // 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。  
randomizedSet.getRandom(); // getRandom 应随机返回 1 或 2 。  
randomizedSet.remove(1); // 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。  
randomizedSet.insert(2); // 2 已在集合中，所以返回 false 。  
randomizedSet.getRandom(); // 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。  

-231 <= val <= 231 - 1
在调用getRandom方法时，数据结构中 至少存在一个 元素。

二、代码

思路：
【1】变长数组List可以在O(1)的时间内完成获取随机元素操作，但是由于无法在O(1)的时间内判断元素是否存在，因此不能在O(1)的时间内完成插入和删除操作。
【2】哈希表可以在O(1)的时间内完成插入和删除操作，但是由于无法根据下标定位到特定元素，因此不能在O(1)的时间内完成获取随机元素操作。
【3】为了满足插入、删除和获取随机元素操作的时间复杂度都是O(1)，需要将变长数组和哈希表结合，变长数组中存储元素，哈希表中存储每个元素在变长数组中的下标。

// 空间换时间
class RandomizedSet {
    Map<Integer,Integer> map;
    List<Integer> list;
    Random random;

    public RandomizedSet() {
        map = new HashMap<>();
        list = new ArrayList();
        random = new Random();
    }
    
    public boolean insert(int val) {
        // 判断value是否存在，存在直接返回false
        if(map.containsKey(val)) {
            return false;
        }
        // 插入 0(1) 使用 map[key = val , value = index] 数组的长度=数据的下标
        map.put(val, list.size());
        // list中存放 val
        list.add(val);
        return true;
    }
    
    // 删除操作的重点在于将变长数组的最后一个元素移动到待删除元素的下标处，然后删除变长数组的最后一个元素。
    // 该操作的时间复杂度是 O(1)，且可以保证在删除操作之后变长数组中的所有元素的下标都连续，方便插入操作和获取随机元素操作。
    public boolean remove(int val) {
        if (!map.containsKey(val)) {
            return false;
        }
        // 思想：list 的 udpate 是 O(1) 所以使用 list中的最后一个元素修改 index 下表的元素
        // 通过map获取指定val的下表
        int index = map.get(val);
        // 获取list中最后一个元素
        int last = list.get(list.size() - 1);
        // 使用最后一个元素替换list中的index元素
        list.set(index, last);
        // map 也需要更新最后一个元素 last 的下标
        map.put(last, index);
        // 删除list和map
        list.remove(list.size() - 1);
        map.remove(val);
        return true;
    }
    
    // 获取随机元素操作时，由于变长数组中的所有元素的下标都连续，因此随机选取一个下标，返回变长数组中该下标处的元素
    public int getRandom() {
        int randomIndex = random.nextInt(list.size());
        return list.get(randomIndex);
    }
}

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

变长数组 + 哈希表： 这道题要求实现一个类，满足插入、删除和获取随机元素操作的平均时间复杂度为O(1)。

变长数组可以在O(1)的时间内完成获取随机元素操作，但是由于无法在O(1)的时间内判断元素是否存在，因此不能在O(1)的时间内完成插入和删除操作。哈希表可以在O(1)的时间内完成插入和删除操作，但是由于无法根据下标定位到特定元素，因此不能在O(1)的时间内完成获取随机元素操作。为了满足插入、删除和获取随机元素操作的时间复杂度都是O(1)，需要将变长数组和哈希表结合，变长数组中存储元素，哈希表中存储每个元素在变长数组中的下标。

插入操作时，首先判断val是否在哈希表中，如果已经存在则返回false，如果不存在则插入val，操作如下：
1、在变长数组的末尾添加val；
2、在添加val之前的变长数组长度为val所在下标index，将val和下标index存入哈希表；
3、返回true。

删除操作时，首先判断val是否在哈希表中，如果不存在则返回false，如果存在则删除val，操作如下：
1、从哈希表中获得val的下标index；
2、将变长数组的最后一个元素last移动到下标index处，在哈希表中将last的下标更新为index；
3、在变长数组中删除最后一个元素，在哈希表中删除val；
4、返回true。

删除操作的重点在于将变长数组的最后一个元素移动到待删除元素的下标处，然后删除变长数组的最后一个元素。该操作的时间复杂度是 O(1)，且可以保证在删除操作之后变长数组中的所有元素的下标都连续，方便插入操作和获取随机元素操作。

获取随机元素操作时，由于变长数组中的所有元素的下标都连续，因此随机选取一个下标，返回变长数组中该下标处的元素。

class RandomizedSet {
    List<Integer> nums;
    Map<Integer, Integer> indices;
    Random random;

    public RandomizedSet() {
        nums = new ArrayList<Integer>();
        indices = new HashMap<Integer, Integer>();
        random = new Random();
    }

    public boolean insert(int val) {
        if (indices.containsKey(val)) {
            return false;
        }
        int index = nums.size();
        nums.add(val);
        indices.put(val, index);
        return true;
    }

    public boolean remove(int val) {
        if (!indices.containsKey(val)) {
            return false;
        }
        int index = indices.get(val);
        int last = nums.get(nums.size() - 1);
        nums.set(index, last);
        indices.put(last, index);
        nums.remove(nums.size() - 1);
        indices.remove(val);
        return true;
    }

    public int getRandom() {
        int randomIndex = random.nextInt(nums.size());
        return nums.get(randomIndex);
    }
}

时间复杂度： 初始化和各项操作的时间复杂度都是O(1)。
空间复杂度： O(n)，其中 nnn 是集合中的元素个数。存储元素的数组和哈希表需要O(n)的空间。