705.Design HashSet

Ссылка на задачу: https://leetcode.com/problems/design-hashset/description/

Описание

Спроектируйте хеш-сет без использования каки-либо встроенных библиотек, в которых уже есть реализация хеш-таблиц и прочего.

Имплементация класса MyHashSet:

• имеет метод void add(key), который вставляет значение key в хеш-сет

• имеет метод bool contains(key), который проверяет, есть ли элемент key в хеш-сете или нет

• имеет метод void remove(key), который удаляет значение key, если элемент есть в хеш-сете, не делает ничего, если элемента нет

Примеры

Пример 1

Input:

Output:

Объяснение:

• первая операция MyHashSet - конструирование объекта

• add 1 - добавление единицы; хеш-сет стал [1]

• add 2 - добавление двойки; хеш-сет стал [1, 2]

• contains 1 - проверка, есть ли элемент 1 в хеш-сете (true)

• contains 3 - проверка, есть ли элемент 3 в хеш-сете (false)

• add 2 - добавление уже имеющейся двойки; хеш-сет не изменился [1, 2]

• contains 2 - проверка, есть ли элемент 2 в хеш-сете (true)

• remove 2 - удаление двойки, хеш-сет стал [1]

• contains 2 - проверка, есть ли элемент 2 в хеш-сете (false)

Ограничения

• 0 <= key <= 10^6

• максимальное количество вызовов add, remove и contains составит 10^4.

Решение

Вспомним определение структуры данных хеш-сет. Данная структура данных хранит только уникальные элементы, причем доступ до элемента, его добавление и удаление - операции, сложность которых О(1), то есть не зависит от размера структуры. Строгость порядка элементов отсутствует, то есть он не гарантирован.

Задача сводится к тому, чтобы придумать, как спроектировать класс MyHashSet, удовлетворяющий всем этим условиям. Интуитивно понятно, что нужно использовать какой-то фундаментальный контейнер “под капотом”. Но какой?

Будем идти по порядку условий:

• доступ до элемента за константное время: мы знаем, что обращение к элементу массива по его индексу происходит за константное время

• добавление элемента за константное время: к массиву можно прибавить элемент за О(1), но только в том случае, если его емкость позволяет нам это сделать

• удаление элемента за константное время: здесь массив не подойдет, так как удаление элемента с произвольной позиции приведет к сдвигу всех элементов справа от удаленного на 1 влево

Как будто бы массив почти подходит. Два фактора мешают его использовать: необходимость иметь достаточную емкость для добавления элемента за О(1) и сдвиг элементов при удалении. Нужно как-то нивелировать эти недостатки.

Первую проблему можно решить, обратившись к ограничениям задачи. Сказано, что key лежит в диапазоне от 0 до 10^6 включительно. Так, если мы заранее выделим память под 1000001 целочисленных элементов, то нам всегда хватит емкости с 100%-ной гарантией. Действительно, если key принять за индекс массва, то максимальный индекс - это 10^6, значит размер массива должен быть 1000001, чтобы никогда не выйти за его границы.

В таком подходе вторая проблема тоже решается. Выделив память заранее под самый максимально длинный массив, мы откинули в строноу проблему сдвига элементов при удалении. Вместо сдвига элементов при удалении мы будем приравнивать удаляемому элементу с индексом key некоторое специальное значение. Таким значением может являться False. False - элемента нет, True - элемент есть.

Алгоритм:

1. Инициализировать массив булевых значений размером 1000001

2. Присвоить всем элементам значение False (пустой хеш-сет)

3. В случае проверки наличия элемента key нужно проверить, равен ли элемент с индексом key значению True

4. При добавлении элемента key достаточно присвоить True элементу массива с индексом key

5. При удалении элемента key достаточно присвоить False элементу массива с индексом key

Код:

python

class MyHashSet:
    def __init__(self):
        self.values = [False] * (10**6 + 1)

    def add(self, key: int) -> None:
        self.values[key] = True

    def remove(self, key: int) -> None:
        self.values[key] = False

    def contains(self, key: int) -> bool:
        return self.values[key]

C++

class MyHashSet {
public:
    MyHashSet() {
        for (int i = 0; i < 1000001; ++i) {
            arr_[i] = false;
        }
    }
    
    void add(int key) {
        arr_[key] = true;
    }
    
    void remove(int key) {
        arr_[key] = false;
    }
    
    bool contains(int key) {
        return arr_[key];
    }
private:
    bool arr_[1000001];
};

Примечание: по идее bool в C++ должен занимать 1 бит (0 или 1), но он занимает 1 байт, так как минимальное адресуемое пространство памяти - 1 байт. Так, в массиве bool arr[1000001] все равно каждый элемент занимает 1 байт. Однако, хорошо зная C++, можно применить трюк с использованием std::vector<bool>, так как std::vector<bool> - это специализированный шаблон, а не обычный контейнер std::vector.

Сложность

Наш хеш-сет удовлетворяет всем требованиям:

• сложность проверки наличия элемента - О(1)

• сложность вставки элемента - О(1)

• сложность удаления элемента - О(1)