Описание:

Като е даден масив от цели числа 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() ), ако го направи, функцията връща, в противен случай ще натисне стойността на . Функцията ще се върне, ако всички елементи на numsса уникални.

Пуснах кода и получих зелена отметка от Leetcode 🙂, така че реших да изпратя и ето статистиката:

Това, което ми направи впечатление на първо място, беше фактът, че бия всички подавания на Leetcode, това не е страхотно, но няма да е за първи път, също така никога не съм минавал през тази точка … това, което обикновено правя след това, е да премина към друг проблем, който в крайна сметка бих напуснал, и да се тревожа за по-добро решение или какво кара кода да се представя толкова лошо по-късно, но не го направих този път...

Реших да разгледам решението отново и наистина да се опитам да разбера сложността, използвам for цикъл, за да повторя, така че това ще бъде сложност, вътре в for цикъла, който използвам, който също има O(n) сложност, тъй като обхожда всеки елемент в масива, за да определи дали е включена определена стойност, което прави общата сложност на решението: O(n²).

Мислех, че ако мога да намеря по-добър начин да проверя дали дадена стойност е включена, мога да подобря сложността. Открих Javascript и научих, че има O(1) сложност за търсене на стойности. Ревизирах първоначалните си стъпки, за да внедря вместо масив:

  • Създайте новнабор за съхраняване на уникални стойности
  • Преминете през всеки елемент в nums, ако newSet вече има върнат елемент true в противен случай добавете елемент към новнабор
  • Връща falseако всички елементи nums са уникални

Изпълних кода, получих зелена отметка от Leetcode 🙂 и след това изпратих:

Бях във възторг, преминах от побеждаване само на 10% от подаванията на „Leetcode“ до побеждаване на над 99%, добър път „Set()“🙂 Предполагам, че наистина има значение каква структура от данни в крайна сметка избирате да съхранявате вашите данни.

Първоначално публикувано в http://codemghrib.wordpress.com на 12 януари 2023 г.