381

381. Insert Delete GetRandom O(1) - Duplicates allowed (Hard)

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

Related Topics:
Array, Hash Table, Design

Similar Questions:

• Insert Delete GetRandom O(1) (Medium)

Solution 1.

// OJ: https://leetcode.com/problems/insert-delete-getrandom-o1-duplicates-allowed/
// Author: github.com/lzl124631x
// Time: O(1) for all
// Space: O(N)
class RandomizedCollection {
    vector<pair<int, int>> v; // value, index among the numbers of the same value
    unordered_map<int, vector<int>> m; // value to indexes in `v`
public:
    RandomizedCollection() {}
    bool insert(int val) {
        bool ans = m.count(val);
        m[val].push_back(v.size());
        v.emplace_back(val, m[val].size() - 1);
        return ans;
    }
    bool remove(int val) {
        auto it = m.find(val);
        if (it == m.end()) return false;
        auto &last = v.back();
        m[last.first][last.second] = m[val].back();
        v[m[val].back()] = last;
        m[val].pop_back();
        if (m[val].empty()) m.erase(val);
        v.pop_back();
        return true;
    }
    int getRandom() {
        return v[rand() % v.size()].first;
    }
};