Задача: 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(): Возвращать случайный элемент из списка, обеспечивая равновероятное распределение на основе количества вхождений каждого элемента.

😎 Решение:

import java.util.*;

public class RandomizedCollection {
    private Map<Integer, Set<Integer>> dict;
    private List<Integer> list;
    private Random rand;

    public RandomizedCollection() {
        dict = new HashMap<>();
        list = new ArrayList<>();
        rand = new Random();
    }

    public boolean insert(int val) {
        boolean exists = dict.containsKey(val);
        if (!exists) {
            dict.put(val, new HashSet<>());
        }
        dict.get(val).add(list.size());
        list.add(val);
        return !exists;
    }

    public boolean remove(int val) {
        if (!dict.containsKey(val) || dict.get(val).isEmpty()) {
            return false;
        }
        int index = dict.get(val).iterator().next();
        dict.get(val).remove(index);
        int lastElement = list.get(list.size() - 1);
        list.set(index, lastElement);
        dict.get(lastElement).add(index);
        dict.get(lastElement).remove(list.size() - 1);
        list.remove(list.size() - 1);
        if (dict.get(val).isEmpty()) {
            dict.remove(val);
        }
        return true;
    }

    public int getRandom() {
        return list.get(rand.nextInt(list.size()));
    }
}

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