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

381. Insert Delete GetRandom O(1) - Duplicates allowed
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);
}