Сложность: 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(): Возвращать случайный элемент из списка, обеспечивая равновероятное распределение на основе количества вхождений каждого элемента.
😎 Решение:
class RandomizedCollection {
private var dict: [Int: Set<Int>]
private var list: [Int]
init() {
dict = [Int: Set<Int>]()
list = [Int]()
}
func insert(_ val: Int) -> Bool {
let exists = dict[val] != nil
if !exists {
dict[val] = Set<Int>()
}
dict[val]?.insert(list.count)
list.append(val)
return !exists
}
func remove(_ val: Int) -> Bool {
guard let indices = dict[val], !indices.isEmpty else {
return false
}
let index = indices.first!
dict[val]?.remove(index)
let lastElement = list.removeLast()
if index < list.count {
list[index] = lastElement
dict[lastElement]?.remove(list.count)
dict[lastElement]?.insert(index)
}
if dict[val]?.isEmpty ?? false {
dict[val] = nil
}
return true
}
func getRandom() -> Int {
return list.randomElement()!
}
}Ставь 👍 и забирай 📚 Базу знаний