381. Insert Delete GetRandom O(1) - Duplicates allowed
Design a data structure that supports all following operations in average O(1) time.
Note: Duplicate elements are allowed.
insert(val)
: Inserts an item val to the collection.remove(val)
: Removes an item val from the collection if present.getRandom
: Returns a random element from current collection of elements. The probability of each element being returned is linearly related to the number of same value the collection contains.
Example:
// Init an empty collection. RandomizedCollection collection = new RandomizedCollection(); // Inserts 1 to the collection. Returns true as the collection did not contain 1. collection.insert(1); // Inserts another 1 to the collection. Returns false as the collection contained 1. Collection now contains [1,1]. collection.insert(1); // Inserts 2 to the collection, returns true. Collection now contains [1,1,2]. collection.insert(2); // getRandom should return 1 with the probability 2/3, and returns 2 with the probability 1/3. collection.getRandom(); // Removes 1 from the collection, returns true. Collection now contains [1,2]. collection.remove(1); // getRandom should return 1 and 2 both equally likely. collection.getRandom();
Rust Solution
use rand::prelude::*;
use std::collections::BinaryHeap;
use std::collections::HashMap;
#[derive(Debug)]
struct RandomizedCollection {
rng: ThreadRng,
indexes: HashMap<i32, BinaryHeap<usize>>,
choices: Vec<i32>,
}
impl RandomizedCollection {
fn new() -> Self {
let rng = thread_rng();
let indexes = HashMap::new();
let choices = vec![];
RandomizedCollection {
rng,
indexes,
choices,
}
}
fn insert(&mut self, val: i32) -> bool {
let ids = self.indexes.entry(val).or_default();
ids.push(self.choices.len());
self.choices.push(val);
ids.len() == 1
}
fn remove(&mut self, val: i32) -> bool {
if let Some(ids) = self.indexes.get_mut(&val) {
if let Some(index) = ids.pop() {
let last_index = self.choices.len() - 1;
let last_value = self.choices[last_index];
if last_value != val {
let other_ids = self.indexes.get_mut(&last_value).unwrap();
other_ids.pop();
other_ids.push(index);
self.choices.swap(index, last_index);
}
self.choices.pop();
true
} else {
false
}
} else {
false
}
}
fn get_random(&mut self) -> i32 {
self.choices[self.rng.gen_range(0, self.choices.len())]
}
}
#[test]
fn test() {
let mut obj = RandomizedCollection::new();
assert_eq!(obj.remove(0), false);
// dbg!(&obj);
// assert_eq!(obj.insert(1), false);
// dbg!(&obj);
// assert_eq!(obj.insert(2), true);
// dbg!(&obj);
// assert_eq!(obj.insert(2), false);
// dbg!(&obj);
// assert_eq!(obj.insert(2), false);
// dbg!(&obj);
// assert_eq!(obj.remove(1), true);
// dbg!(&obj);
// assert_eq!(obj.remove(1), true);
// dbg!(&obj);
// assert_eq!(obj.remove(2), true);
// dbg!(&obj);
// assert_eq!(obj.insert(1), true);
// dbg!(&obj);
// assert_eq!(obj.remove(2), true);
}
Having problems with this solution? Click here to submit an issue on github.