【Day 6】 2020-06-06 - 380. 常数时间插入、删除和获取随机元素.md

【Day 6】 2020-06-06 - 380. 常数时间插入、删除和获取随机元素

题目

设计一个支持在平均 时间复杂度 O(1) 下，执行以下操作的数据结构。

insert(val)：当元素 val 不存在时，向集合中插入该项。

remove(val)：元素 val 存在时，从集合中移除该项。

getRandom：随机返回现有集合中的一项。每个元素应该有相同的概率被返回。

示例 :

// 初始化一个空的集合。

RandomizedSet randomSet = new RandomizedSet();

// 向集合中插入 1 。返回 true 表示 1 被成功地插入。

randomSet.insert(1);

// 返回 false ，表示集合中不存在 2 。

randomSet.remove(2);

// 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。

randomSet.insert(2);

// getRandom 应随机返回 1 或 2 。

randomSet.getRandom();

// 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。

randomSet.remove(1);

// 2 已在集合中，所以返回 false 。

randomSet.insert(2);

// 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。

randomSet.getRandom();

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/insert-delete-getrandom-o1

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

• 用HashMap和ArrayList结合，完成O(1)的操作。
• HashMap用来存放当前数组中value和下标index的键值对，添加时，先在HashMap中put这个数和当前数组的长度，例如数组中已经有了[0, 1]，这时如果要添加数字2进入数组，先把 (key = 2, value = nums.size()) 添加到HashMap中，即代表待插入数字2所在的下标为2，最后再把数字2加入到nums数组中（末尾）
• 对于删除操作，先判断待删除的数是否在数组中排最末尾，若是，直接remove。否则，思想就是把nums数组中最后一个数当做“覆盖数”，去覆盖要删除的数，因为我们在HashMap中都存放了每个数的下标，那么直接找出待删除数字的下标，覆盖之后，只需要把nums中最后一个数remove掉，并且更改HashMap中原来“覆盖数”的下标。

代码：

import java.util.Random;
class RandomizedSet {
    
    ArrayList<Integer> nums;
    HashMap<Integer, Integer> poss;
    Random rand = new Random();
    
    /** Initialize your data structure here. */
    public RandomizedSet() {
        nums = new ArrayList<Integer>();
        poss = new HashMap<Integer, Integer>();
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
        boolean exist = poss.containsKey(val);
        if (exist)
            return false;
        poss.put(val, nums.size());
        nums.add(val);
        return true;
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        boolean exist = poss.containsKey(val);
        if (!exist)
            return false;
        int pos  = poss.get(val);
        // check if it's lastone
        if (pos < nums.size() - 1) {
            // swap the lastone with val
            int temp = nums.get(nums.size() -1);
            nums.set(pos, temp);
            poss.put(temp, pos);
        }
        poss.remove(val);
        nums.remove(nums.size() - 1);
        return true;
    }
    
    /** Get a random element from the set. */
    public int getRandom() {
        return nums.get(rand.nextInt(nums.size()));
    }
}