Описание:
Дан целочисленный массив nums, вернуть true, если какое-либо значение встречается в массиве не менее двух раз, и вернуть false, если каждый элемент различен.
Пример 1:
Input: nums = [1,2,3,1] Output: true
Пример 2:
Input: nums = [1,2,3,4] Output: false
Пример 3:
Input: nums = [1,1,1,3,3,4,3,2,4,2] Output: true
Когда я столкнулся с этой проблемой Leetcode, я сначала подумал о создании дополнительного массива для хранения различных значений, а затем сравнил их со значениями в массиве. Мои размышления привели к следующим шагам:
- Создайте новый массив для хранения уникальных значений.
- Пройтись по каждому элементу в nums, если новый массив уже содержит элемент, вернуть true в противном случае элемент переместить в новый массив
- Возвращает false, если все элементы nums уникальны.
Чтобы проверить, есть ли в новом массиве уже элемент, я подумал об использовании встроенной функции Javascript, я обнаружил… в этот момент я почувствовал себя достаточно комфортно, чтобы закодировать решение:
Приведенный выше код реализует начальные шаги, как написано... он создает массив с именем new_arr для хранения уникальных значений, он использует цикл for для перебора каждое значение , он проверяет, содержит ли уже это значение (используя Javascript includes() ), если да, то функция возвращает , иначе будет push значение для . Функция вернется, если все элементы nums уникальны.
Я запустил код и получил зеленую галочку у Leetcode 🙂 поэтому я решил отправить и вот статистика:
В первую очередь мне бросилось в глаза то, что я обхожу все заявки на Leetcode, это не круто, но это будет не в первый раз, я также никогда не проходил мимо этого момента… то, что я обычно делал дальше, — это переходить к другой проблеме, которую я в конечном итоге бросил, и беспокоиться о лучшем решении или о том, что заставляет код работать так плохо позже, но я не сделал этого в этот раз…
Я решил снова посмотреть на решение и действительно попытаться понять сложность, я использую цикл for для повторения, чтобы это было сложностью, внутри цикла for, который я использую, который также имеет O (n) сложность, так как он выполняет итерацию по каждому элементу массива, чтобы определить, включено ли конкретное значение, в результате чего общая сложность решения составляет O(n²).
Я подумал, что если я смогу найти лучший способ проверить, включено ли значение, я смогу повысить сложность. Я открыл для себя Javascript и узнал, что он имеет O(1) сложность для поиска значений. Я пересмотрел свои первоначальные шаги, чтобы теперь реализовать a вместо массива:
- Создайте новыйSet для хранения уникальных значений.
- Пройдитесь по каждому элементу в nums, если newSet уже содержит элемент return true иначе добавить элемент в новыйSet
- Возвращает false, если все элементы nums уникальны.
Я запустил код, получил зеленую галочку от Leetcode 🙂 и отправил:
Я был в восторге, я прошел путь от 10 % заявок на Leetcode до более чем 99 %, путь к Set() 🙂 Думаю, действительно важно, какую структуру данных вы в конечном итоге выберете для хранения своих данных.
Первоначально опубликовано на http://codemghrib.wordpress.com 12 января 2023 г.
