[LeetCode] 380. Insert Delete GetRandom O(1)

Design a data structure that supports all following operations in average O(1) time.

insert(val): Inserts an item val to the set if not already present.
remove(val): Removes an item val from the set if present.
getRandom: Returns a random element from current set of elements.
Each element must have the same probability of being returned.

Example:
// Init an empty set.
RandomizedSet randomSet = new RandomizedSet();

// Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomSet.insert(1);

// Returns false as 2 does not exist in the set.
randomSet.remove(2);

// Inserts 2 to the set, returns true. Set now contains [1,2].
randomSet.insert(2);

// getRandom should return either 1 or 2 randomly.
randomSet.getRandom();

// Removes 1 from the set, returns true. Set now contains [2].
randomSet.remove(1);

// 2 was already in the set, so return false.
randomSet.insert(2);

// Since 2 is the only number in the set, getRandom always return 2.
randomSet.getRandom();

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

实现RandomizedSet 类：

RandomizedSet() 初始化 RandomizedSet 对象
bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。
bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。
int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。
你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(1) 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/insert-delete-getrandom-o1
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

大致思路是用一个 hashmap 和一个 list 来实现。其中 list 只是存元素，hashmap 存的是<元素，他在 list 里的下标>。

既然题目对所有操作的复杂度要求都是 O(1)，那么大概率需要用到 hashmap，因为元素本身在 list 中，在不知道 list 下标的情况下去删除一个元素的复杂度肯定是不止 O(1) 的。又因为我们是没有一个数据结构既能支持 O(1) 级别的读取，又能做到有序，所以这里 hashmap 里存的是<元素，他在 list 里的下标>。同时再创建一个 list，只存储元素。

insert 元素的时候，将 val 加入 list，然后将<val, list.size() - 1> 加入 hashmap。这样 hashmap 就记录了这个 val 在 list 里的下标。

remove 一个目标值 val 的时候，如果这个元素不在 hashmap 自然是 return false。若存在，

• 获取 val 在 list 中的 index
• 将 list 中的最后一个元素移动到 index 上
• 更新 hashmap 中最后一个元素的位置
• 从 hashmap 中移除 val

跑一个例子吧，比如一开始加了 1,2,3,4,5 五个数字，他们被加入的时候，hashmap 和 list 应该长类似这样

map: {1:0, 2:1, 3:2, 4:3, 5:4}
list: 1->2->3->4->5

此时如果删除了数字 2，hashmap 和 list 会变成这样，最后一个元素 5 会被移动到 list 上 index 为 1 的地方。
map: {1:0, 5:1, 3:2, 4:3}
list: 1->5->3->4

复杂度

时间O(1)
空间O(n)

代码

Java实现

class RandomizedSet {
    HashMap<Integer, Integer> map;
    List<Integer> list;
    Random rmd;

    /** Initialize your data structure here. */
    public RandomizedSet() {
        map = new HashMap<>();
        list = new ArrayList<>();
        rmd = new Random();
    }

    public boolean insert(int val) {
        if (map.containsKey(val)) {
            return false;
        }
		// 加入val之后，map里存的是val在list中的index，这样比较直观
        list.add(val);
        map.put(val, list.size() - 1);
        return true;
    }

    public boolean remove(int val) {
        if (!map.containsKey(val)) {
            return false;
        }
        int lastItem = list.get(list.size() - 1);
		// 要移除的元素在list中的index
        int index = map.get(val);
		// 把最后一个元素lastItem挪到要移除的元素val的位置
        list.set(index, lastItem);
		// 更新lastItem在map中的index
        map.put(lastItem, index);
        list.remove(list.size() - 1);
        map.remove(val);
        return true;
    }

    public int getRandom() {
        return list.get(rmd.nextInt(list.size()));
    }
}

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