Kotlin | LeetCode

Задача: 380. Insert Delete GetRandom O(1)
Сложность: 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(): Возвращать случайный элемент из списка, используя встроенную функцию генерации случайных чисел.

😎

Решение:

import kotlin.random.Random

class RandomizedSet {
    private val dict = mutableMapOf<Int, Int>()
    private val list = mutableListOf<Int>()

    fun insert(val: Int): Boolean {
        if (dict.containsKey(val)) {
            return false
        }
        dict[val] = list.size
        list.add(val)
        return true
    }

    fun remove(val: Int): Boolean {
        val index = dict[val] ?: return false
        val lastElement = list.removeAt(list.size - 1)
        if (index < list.size) {
            list[index] = lastElement
            dict[lastElement] = index
        }
        dict.remove(val)
        return true
    }

    fun getRandom(): Int {
        return list[Random.nextInt(list.size)]
    }
}

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

Please open Telegram to view this post