前言

今天来搞一道不同寻常的，难度中等。

题目

实现RandomizedSet 类：

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

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

示例：

提示：

• -231 <= val <= 231 - 1
• 最多调用 insert、remove 和 getRandom 函数 2 * ``105 次
• 在调用 getRandom 方法时，数据结构中 至少存在一个 元素。

分析

这道题咋一看很简单，借助字典/map以值做下标，以下标做值就可以轻松做到O(1)的查询时间，但是当你写到get_random的时候你就犯难了，因为Rust中我们只能用Hashmap，然而Hashmap是非连续的，我们可以记录len, 但是当我们删除其中一个元素，我们能做的只是len - 1，没办法记录是哪个发生了变化，那么要么我们再搞个数组用来记录，但是时间复杂度就不是O(1)了，所以我们要想一个方法，这个方法要支持所有下标的记录，又可以在删除元素的时候动态调整元素位置，并且都是发生在O(1)时间复杂度下的，那就意味着不能遍历，删除之后的动态调整也得是直接处理对应的下标或者常数下的操作比如操作它前后或者整个数组的前后元素。

诶，这不就有思路了，如果我们删除中间的元素，用最后的元素来补充，这不就满足了常数时间内调整，并且整个数组中间没有空缺的问题？

不过这里还有个点需要解决：我们要怎么设计才能做到上面的效果？

一个hashmap是不能满足的，因为我们还需要记录下标，得知道是哪个被删除了,同时还要将最后一个元素插入到被删除的这个位置，那么这里至少还得有一个数组，当然，到这一步你可能想着不用数组，单独记录最后一个就行。然而不行，get_random还需要随机返回对应的元素，但是我们的hashmap的k-v是：value-index，是做不到通过下标找到元素的，所以我们还需要一个数组来做到k-v是index-value。

我们先捋一捋几个点：

1. 找到删除的下标需要O(1);
2. 找到对应的元素需要O(1);
3. 找到下标通过value；
4. 找到元素通过index；

那么我们可以：

1. 使用hashmap做到通过value找index时间为O(1);
2. 使用vector做到通过index找value时间为O(1);

那么一切就豁然开朗了，：

1. 我们用hashmap保存vector的下标，用vector保存元素值
2. 删除元素时通过hashmap拿到下标，然后删除vector对应的元素，再将vector最后一个元素移动到对应的位置，然后更新最后一个元素在hashmap中对应的索引值为之前删除的那个下标。
3. 最后len - 1。

解

代码稍微有些乱

我这里还傻傻的自己写了个根据时间来计算随机值的方法，其实可以直接用range这个crate。

测试用例

总结

这道题有些灵活，关键点在于如何在删除元素后保留一条完整连续的下标索引。