前言#
今天来搞一道不同寻常的，难度中等。
题目#
实现RandomizedSet 类：
RandomizedSet()初始化RandomizedSet对象bool insert(int val)当元素val不存在时，向集合中插入该项，并返回true；否则，返回false。bool remove(int val)当元素val存在时，从集合中移除该项，并返回true；否则，返回false。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- 最多调用
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。
我们先捋一捋几个点：
- 找到删除的下标需要
O(1); - 找到对应的元素需要
O(1); - 找到下标通过
value； - 找到元素通过
index；
那么我们可以：
- 使用
hashmap做到通过value找index时间为O(1); - 使用
vector做到通过index找value时间为O(1);
那么一切就豁然开朗了，：
我们用hashmap保存vector的下标，用vector保存元素值删除元素时通过hashmap拿到下标，然后删除vector对应的元素，再将vector最后一个元素移动到对应的位置，然后更新最后一个元素在hashmap中对应的索引值为之前删除的那个下标。最后len - 1。
解#
代码稍微有些乱
#[derive(Debug)]
struct RandomizedSet {
pub hash: HashMap<i32, usize>,
pub idx: Vec<i32>,
pub last: usize,
}
use std::hash::{Hash, Hasher};
use std::time::SystemTime;
// A struct that implements the Hash trait
#[derive(Hash)]
struct TimeHash {
time: SystemTime,
}
// A function that returns a random u64 number
fn random_number(len: usize) -> u64 {
// Create a new instance of TimeHash with the current time
let time_hash = TimeHash {
time: SystemTime::now(),
};
// Create a new instance of a default hasher
let mut hasher = std::collections::hash_map::DefaultHasher::new();
// Hash the TimeHash instance
time_hash.hash(&mut hasher);
// Get the hash value as a u64 number
let hash_value = hasher.finish();
// Return the hash value as the random number
hash_value % len as u64
}
/**
* `&self` means the method takes an immutable reference.
* If you need a mutable reference, change it to `&mut self` instead.
*/
impl RandomizedSet {
fn new() -> Self {
let hash: HashMap<i32, usize> = HashMap::new();
Self {
hash, // hash值存储idx中的下标
idx: vec![0; 2 * 10_usize.pow(5)],
last: 0,
}
}
fn insert(&mut self, val: i32) -> bool {
match self.hash.get(&val) {
None => {
// 将下标放置到hashmap上，将值放入到idx中，同时更新指向数组最后一个元素的指针
self.hash.insert(val, self.last);
self.idx[self.last] = val;
self.last += 1;
dbg!(&self.last);
dbg!(&self.idx.get(0..self.last));
return true
}
Some(_) => false,
}
}
fn remove(&mut self, val: i32) -> bool {
if self.hash.get(&val) == None {
return false;
}
// 这一步比较复杂，我们需要先拿到hashmap中的下标，然后再删除idx中对应下标的元素
// 接着将idx中最后一个元素填充到里面，然后删除最后一个元素在hashmap中的下标
let remove_index = *self.hash.get(&val).unwrap();
// 特殊场景，移除的元素正好是最后一个
if remove_index == self.last - 1 {
self.hash.remove(&val);
self.idx.remove(self.last - 1);
} else {
self.idx.splice(
remove_index as usize..=remove_index as usize,
[self.idx[self.last - 1]],
);
// 删除被移除元素在hashmap上的索引，这样这个元素就彻底不存在了。
self.hash.remove(&val);
let new_val = self.idx.remove(self.last - 1);
// 更新hashmap上被移动的最后一个元素的下标，指向之前删除的位置
self.hash.insert(new_val, remove_index);
}
// 将最后一个元素放置到需要删除的元素的位置
self.last -= 1;
dbg!(&self.last);
dbg!(&self.idx.get(0..self.last));
return true;
}
fn get_random(&mut self) -> i32 {
let ran = random_number(self.last);
return self.idx[ran as usize];
}
}我这里还傻傻的自己写了个根据时间来计算随机值的方法，其实可以直接用range这个crate。
测试用例#
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_randomized_set() {
let mut set = RandomizedSet::new();
/// ["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
/// [[], [1], [2], [2], [], [1], [2], []]
/// 输出
/// [null, true, false, true, 2, true, false, 2]
// assert_eq!(set.insert(1), true);
// assert_eq!(set.remove(2), false);
// assert_eq!(set.insert(2), true);
// assert_eq!(set.get_random(), 2);
// assert_eq!(set.remove(1), true);
// assert_eq!(set.insert(2), false);
// assert_eq!(set.get_random(), 2);
// ["RandomizedSet","insert","remove","insert","getRandom","remove","insert","getRandom"]
// [[],[-1],[-2],[-2],[],[-1],[-2],[]]
// assert_eq!(set.insert(-1), true);
// assert_eq!(set.remove(-2), false);
// assert_eq!(set.insert(-2), true);
// assert_eq!(set.get_random(), -1);
// assert_eq!(set.remove(-1), true);
// assert_eq!(set.insert(-2), false);
// assert_eq!(set.get_random(), -2);
// ["RandomizedSet","remove","remove","insert","getRandom","remove","insert"]
// [[],[0],[0],[0],[],[0],[0]]
// [null,false,false,true,0,true,true]
assert_eq!(set.remove(0), false);
assert_eq!(set.remove(0), false);
assert_eq!(set.insert(0), true);
assert_eq!(set.get_random(), 0);
assert_eq!(set.remove(0), true);
assert_eq!(set.insert(0), true);
}
}总结#
这道题有些灵活，关键点在于如何在删除元素后保留一条完整连续的下标索引。