Задача: 381. Insert Delete GetRandom O(1) - Duplicates allowed
Сложность: hard

RandomizedCollection — это структура данных, содержащая набор чисел, возможно с дубликатами (т.е. мультимножество). Она должна поддерживать вставку и удаление определенных элементов, а также предоставление случайного элемента.
Реализуйте класс RandomizedCollection:
RandomizedCollection(): Инициализирует пустой объект RandomizedCollection.
bool insert(int val): Вставляет элемент val в мультимножество, даже если элемент уже присутствует. Возвращает true, если элемента не было, и false в противном случае.
bool remove(int val): Удаляет элемент val из мультимножества, если он присутствует. Возвращает true, если элемент присутствовал, и false в противном случае. Если у val несколько вхождений в мультимножестве, удаляется только одно из них.
int getRandom(): Возвращает случайный элемент из текущего мультимножества. Вероятность возврата каждого элемента пропорциональна числу вхождений этого элемента в мультимножество.
Реализуйте функции класса так, чтобы каждая функция работала в среднем за O(1) времени.

Пример:

Input
["RandomizedCollection", "insert", "insert", "insert", "getRandom", "remove", "getRandom"]
[[], [1], [1], [2], [], [1], []]
Output
[null, true, false, true, 2, true, 1]

👨‍💻 Алгоритм:

1⃣Создать словарь для хранения значений и их индексов в списке, а также список для хранения всех элементов мультимножества.

2⃣Метод insert(val): Добавить значение в конец списка и обновить словарь, добавив индекс этого значения. Возвращать true, если значение отсутствовало ранее, и false в противном случае.
Метод remove(val): Удалить одно вхождение значения из словаря и списка. Для удаления значения заменить его последним элементом списка и обновить словарь. Возвращать true, если значение присутствовало, и false в противном случае.

3⃣Метод getRandom(): Возвращать случайный элемент из списка, обеспечивая равновероятное распределение на основе количества вхождений каждого элемента.

😎 Решение:

using namespace std;

class RandomizedCollection {
public:
    RandomizedCollection() {}

    bool insert(int val) {
        bool exists = dict.find(val) != dict.end();
        if (!exists) {
            dict[val] = unordered_set<int>();
        }
        dict[val].insert(list.size());
        list.push_back(val);
        return !exists;
    }

    bool remove(int val) {
        if (dict.find(val) == dict.end() || dict[val].empty()) {
            return false;
        }
        int index = *dict[val].begin();
        dict[val].erase(index);
        int lastElement = list.back();
        list[index] = lastElement;
        dict[lastElement].insert(index);
        dict[lastElement].erase(list.size() - 1);
        list.pop_back();
        if (dict[val].empty()) {
            dict.erase(val);
        }
        return true;
    }

    int getRandom() {
        int randomIndex = rand() % list.size();
        return list[randomIndex];
    }

private:
    unordered_map<int, unordered_set<int>> dict;
    vector<int> list;
};

Ставь 👍 и забирай 📚 Базу знаний