Хэш-таблица — это структура данных, содержащая пары ключ-значение, где можно изменить значение, а также добавить или удалить пару ключ-значение. Эквивалентом ключа хеш-таблицы в массиве будет индекс, однако в массиве индекс устанавливается по местоположению с индексом, начинающимся с 0 и увеличивающимся оттуда. В хеш-таблице можно установить ключ. Когда дело доходит до временной сложности Big O, различия между массивами и хеш-таблицами становятся более очевидными. Поиск, вставка и удаление выполняются за O(n) в массивах, но за O(1) для хеш-таблиц. Поиск идентичен для обоих. Этот пост покажет, как использование хеш-таблицы для поиска первого повторяющегося числа в массиве может снизить временную сложность Big O. Однако сложность пространства Big O будет увеличена.
Самый простой подход — использовать вложенный цикл, в котором мы перебираем массив, сравнивая числа, сначала сравнивая первое со вторым, затем с третьим и т. д. Затем то же самое делается со вторым числом, сравнивая его с каждым последующим числом. Когда совпадение найдено, возвращается совпавший номер. Если совпадений не найдено, возвращается undefined. Этот подход может быть дорогостоящим с точки зрения времени, поскольку, если совпадение происходит между двумя последними числами, потребуется несколько итераций. Как обычно для вложенных циклов, временная сложность Big O равна O(n²), а пространственная сложность равна O(1), поскольку новые объекты не создаются. Кодирование для простейшего подхода может быть следующим:
Подход с целью снижения временной сложности состоял бы в создании хеш-таблицы и последовательном размещении чисел из массива в хэш-таблицу в качестве ключей. Если этот номер уже существует в качестве ключа, мы останавливаемся и возвращаем этот номер. Если этот номер в качестве ключа еще не существует, он добавляется в хеш-таблицу, и мы переходим к следующему числу в массиве. Если совпадений не найдено, возвращается undefined. Для этой функции, которая содержит только один цикл, временная сложность равна O(n), но следует помнить, что, поскольку объект был создан, пространственная сложность теперь составляет O(n) вместо O(1), что представляет собой увеличение. Кодирование для этого подхода может быть следующим:
Спасибо за чтение!
