Описание:
Като е даден масив от цели числа 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 г.