Сложность: medium
Реализуйте класс RandomizedSet:
RandomizedSet(): Инициализирует объект RandomizedSet.
bool insert(int val): Вставляет элемент val в множество, если его там нет. Возвращает true, если элемент отсутствовал, и false в противном случае.
bool remove(int val): Удаляет элемент val из множества, если он присутствует. Возвращает true, если элемент присутствовал, и false в противном случае.
int getRandom(): Возвращает случайный элемент из текущего множества элементов (гарантируется, что по крайней мере один элемент существует при вызове этого метода). Каждый элемент должен иметь равную вероятность быть возвращенным.
Вы должны реализовать функции класса таким образом, чтобы каждая функция работала в среднем за O(1) по времени.
Пример:
Input
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
Output
[null, true, false, true, 2, true, false, 2]
👨💻 Алгоритм:
1⃣Создать словарь для хранения значений и их индексов, а также список для хранения значений.
2⃣Метод insert(val): Проверить наличие значения в словаре. Если отсутствует, добавить значение в список и обновить словарь с новым индексом.
Метод remove(val): Проверить наличие значения в словаре. Если присутствует, заменить удаляемое значение последним элементом списка, обновить его индекс в словаре, удалить последний элемент из списка и удалить значение из словаря.
3⃣Метод getRandom(): Возвращать случайный элемент из списка, используя встроенную функцию генерации случайных чисел.
😎 Решение:
class RandomizedSet {
private var dict: [Int: Int]
private var list: [Int]
init() {
dict = [Int: Int]()
list = [Int]()
}
func insert(_ val: Int) -> Bool {
if dict[val] != nil {
return false
}
dict[val] = list.count
list.append(val)
return true
}
func remove(_ val: Int) -> Bool {
guard let index = dict[val] else {
return false
}
let lastElement = list.removeLast()
if index < list.count {
list[index] = lastElement
dict[lastElement] = index
}
dict[val] = nil
return true
}
func getRandom() -> Int {
return list.randomElement()!
}
}Ставь 👍 и забирай 📚 Базу знаний