## 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.

1. insert(val): Inserts an item val to the collection.
2. remove(val): Removes an item val from the collection if present.
3. 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 {
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);
// assert_eq!(obj.insert(1), false);
// assert_eq!(obj.insert(2), true);
// assert_eq!(obj.insert(2), false);
// assert_eq!(obj.insert(2), false);
// assert_eq!(obj.remove(1), true);
// assert_eq!(obj.remove(1), true);
// assert_eq!(obj.remove(2), true);
// assert_eq!(obj.insert(1), true);
// assert_eq!(obj.remove(2), true);
}

Having problems with this solution? Click here to submit an issue on github.