How to remove duplicates from a sorted array? | Leetcode task

Подписаться 62 тыс.

Просмотров 11 тыс.

50% 1

Привет друзья! У нас для вас очередная задача с Leetcode: leetcode.com/p...
Это задача с простым уровнем сложности, но достаточно популярная на собеседованиях: "Как удалить дубликаты из сортированного массива?".
Про удаление дубликатов из массива мы уже снимали отдельное видео: • Как удалить дубликаты ...
В нем мы рассмотрели 3 различных способа. Но, к сожалению, для решения этой конкретной задачи они все не подойдут. Так как у нас есть важное ограничение - сложность алгоритма по памяти должна быть O(1). Поэтому в этом видео мы разберем с вами еще один алгоритм, в котором мы удалим все дубликаты из отсортированного массива за один проход цикла.
Оставляйте свои получившиеся решения внизу в комментариях, делитесь этим видео с друзьями!
Приятного просмотра!
Код из видео: codepen.io/puz...
---
Если видео было для вас полезным, ставьте лайк и поделитесь им с друзьями.
Подписывайтесь на наш канал: bit.ly/fs-ytb
---
Присоединяйтесь к нам в соцсетях:
FB: / frontendscience
Instagram Сергея Пузанкова: / puzankovcom
Заходите на наш сайт: frontend-scienc...
#javascript #задачи #leetcode #itсобеседование

Опубликовано:

3 окт 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 97

@frontendscience 3 года назад

Варианты решения задачи: codepen.io/puzankov/pen/jOWKawO?editors=0001 1) Со сложностью O(n^2) как в видео 2) Еще один вариант решения со сложность O(n)

@ВоинственныйХомяк-к8р 3 года назад

Задачки которые необходимо решать (практика) это единственное что позволяет развиваться в какой либо сфере. Сергей, спасибо за материал. Хотелось бы побольше разных задач. От себя лично желаю тебе на этой основе больше подписчиков! Буду рекомендовать твой канал всем знакомым, кто связан с этой областью!

@frontendscience 3 года назад

Благодарю за поддержку! Приятно)

@SerzhNesteruk Год назад

Спасибо за интересную задачу! Сперва оформил решение похожим образом, только с циклом в обратную сторону: const removeDuplicates1 = arr => { for (let i = arr.length; i--; ) { if (arr[i] === arr[i - 1]) { arr.splice(i, 1); } } return arr.length; }; Но потом задумался над быстродействием метода splice, и переписал уже без него: const removeDuplicates2 = arr => { let index = 0, value; for (let i = 0; i < arr.length; i++) { if (arr[i] !== value) { arr[index++] = value = arr[i]; } } return arr.length = index; }; На массиве в 100k элементов (и с 66666 дубликатами) новая функция отработала быстрее в 1000 раз (!): const array = Array.from(Array(1e5), (_, i) => Math.floor(i / 3)); console.time('with splice'); console.log(removeDuplicates1(array)); // 33334 console.timeEnd('with splice'); // 2353.233ms console.time('without splice'); console.log(removeDuplicates2(array)); // 33334 console.timeEnd('without splice'); // 2.323ms

@ВейсалТаштанов 4 года назад

Спасибо за очередную задачу!) Сергей, есть еще одна крутая идея - алгоритм нахождения счастливого билета) Недавно решал, но очень хотелось бы увидеть решение такой задачи от Вас)

@frontendscience 4 года назад

Да классная задача. Сделаем!

@denisoleksyuk5346 3 года назад

Звучит интересно 👍

@astrotrain 4 года назад

Обожаю такие задачи с заковыками, вроде как всё очевидно, ан нет.) Главное помнить, что код всегда делает то, что ему сказали делать, если результат не тот, значит ошибка в логике.

@frontendscience 4 года назад

Да они классные. Тренируют думалку :)

@ВадимБєк 4 года назад

Делал задачу перебирая масив обычным циклом, понял в чём получается загвоздка но ни как не мог понять как же её решить пока случайно не увидел минусы в коментах и не осенило.Решение было таким простым казалось бы и в тоже время для меня таким неожиданным, вот и создавай циклы по привычке. Действительно хорошее задание

@frontendscience 4 года назад

Рад, что было полезно! Заказывайте еще видео.

@ВиталийКузнецов-щ3т7й 4 года назад

Спасибо, одно удовольствие смотреть!

@frontendscience 4 года назад

Спасибо Вам, что смотрите и поддерживаете канал! :)

@EvilYou 3 года назад

Сложность алгоритма из видео O (n^2) как я понимаю, так как метод splice сдвигает весь массив. Вот мое решение за O (n): function removeDuplicates(arr) { let lastUnique = null; let lastReplaced = -1; for (let i = 0; i < arr.length; i++) { if (arr[i] !== lastUnique) { lastReplaced++; arr[lastReplaced] = arr[i]; lastUnique = arr[i]; } } arr.length = lastReplaced + 1; // если соответствовать условию из видео, то return lastReplaced + 1; (на leetcode возвращать ничего не надо) } // Runtime: 80 ms, faster than 93.54% // Memory Usage: 41.2 MB, less than 61.17%

@EvilYou Год назад

ух, какое же крутое решение у меня было ))

@Albert_Hall Год назад

Чётко. Пушка. Прослушал с удовольствием.

@странствие 4 года назад

const remove = arr => arr.filter((n, i) => arr.indexOf(n) === i).length Так же проще, вроде. Да с неотсортированным массивом будет работать

@ОлегСелин-ш9ы 4 года назад

Только время работы алгоритма становится O(n*n)

@странствие 4 года назад

@@ОлегСелин-ш9ы я фиг знает, по какому принципу оно считается просто)

@frontendscience 4 года назад

Сложность этого алгоритма выйдет O(n^2). По факту выходит, что в коде цикл в цикле - внутри «цикла» фильтр ( пробегаем весть массив) есть еще один «цикл» поиск indexOf. Решение через фильтр в реальной жизни часто используется, так как обычно у нас не бесконечные массивы и нету такого ограничения по сложности:) да и читается такой вариант намного лучше.

@странствие 4 года назад

@@frontendscience аа, я просто думал indexOf побыстрее работает) Ну ладно Решение, так сказать, для продакшена получилось, а не для задачи)

@frontendscience 4 года назад

Именно! И это круто!

@Sleep88Walker 3 года назад

function removeDuplicates(arr) { let ptr=0; for (let i = 1; i < arr.length; i++) { if (arr[i]!==arr[i-1]) ptr++; arr[ptr]=arr[i]; } arr.length=ptr+1; return ptr+1; } Поправьте если не прав, но splice сдвигает оставшуюся часть массива, т.е проходится по всем элементам справа от удаляемого. мой же метод проходит только 1 раз. Поэтому мне кажется что в худшем случае сложность вашего алгоритма будет равна n^2(если массив заполнен одинаковыми значениями)

@ОлегСелин-ш9ы 4 года назад

Чтобы не вычитать индекс лишний раз, можно иттерироровать массив от конца к началу.

@frontendscience 4 года назад

Да да! Если в обратную сторону идти, то вычитать дополнительно не надо. код на одну строку короче будет :)

@blgarOk 2 года назад

'Тренирует вашу думалку' Улыбныло)

@valeriakan6474 2 года назад

вроде задачка показалась простенькой, а сама запуталась с использванием splice и сдвигом указателя, решила проще использовать экстра-массив спасибо! let removeDuplicatesMy = function (nums) { // guess array is not empty let len = 1; let prev = nums[0]; const res = [prev] for (let i = 1; i < nums.length; i++) { if (nums[i] !== prev) { prev = nums[i]; res.push(prev) len++; } } nums.length = len; nums.forEach((elem, i, arr) => arr[i]=res[i]) return len; }

@frontendscience 2 года назад

Благодарю за решение!

@СергейЕрмаков-д7л 2 года назад

Чтобы не уменьшать i, вроде можно пройтись по массиву в обратном порядке, тогда изменение индексов не помешает

@strikerorion5290 2 года назад

Спасибо, класс!

@Андрей-й9ц6я 4 года назад

Первая реакция на задачу: пффф да это же проще некуда, решил так же как и вы в начале и потом завис минут на 10, пока не дошло, что можно итерироваться по массиву в обратном порядке. jsfiddle.net/Ly8v9q5r/ Собеседование бы точно провалил :)

@frontendscience 4 года назад

Круто! Удачи на собеседовании :)

@Андрей-й9ц6я 4 года назад

@@frontendscience Спасибо, было бы интересно увидеть от вас решение задачи, нахождения кратчайшего пути в однонаправленных взвешенных не циклических графах (алгоритм Дейкстры). Хотя для собеседования может это перебор :)

@yarik83men51 2 года назад

Спасибо за Ваш труд. Мои "5 копеек" на Java, без использования Set: import java.util.ArrayList; import java.util.Arrays; public class RemoveDuplicateInArray { public static void main(String[] args) { int[] array = {1,2,2,1,5,5,3,4,3,3,7,8,7,8,9}; System.out.println(removeDuplicate(array)); } private static int removeDuplicate(int[] arr) { ArrayList list = new ArrayList(arr.length); Arrays.sort(arr); list.add(arr[0]); for (int i = 1; i < arr.length; i++) { if (!list.contains(arr[i])) { list.add(arr[i]); } } return list.size(); } }

@realvall Год назад

вы можете просто добавлять элементы не в лист, а в сет, тогда проверки не нужны будут

@aleksd286 3 года назад

Я бы так сделал (писал с телефона) const fn = arr => { const keys = {} return arr. reduce((prev,curr)=>{ if(!keys[curr]) { prev = prev.push(curr) keys[curr] = 1 } return prev }, []).length

@frontendscience 3 года назад

отличный вариант

@asktosimon 6 месяцев назад

если проходить с конца массива то не надо заморачиваться над смещением

@VasiliyFominykh 5 месяцев назад

Смотрю такой - "Как удалить дубликаты из отсортированного массива? | Задача с Leetcode", о, думаю, дай гляну может чего кроме set предложат. И правда бла-бла-бла splice... О думаю, надо затестить, а потом смотрю - ёпт, это не питон а ява )))

@inoyakaigor 4 месяца назад

Это не Ява)

@VasiliyFominykh 4 месяца назад

@@inoyakaigor да? Ну ладно, но и питон тоже )

@inoyakaigor 4 месяца назад

@@VasiliyFominykh это Яваскрипт =)

@VasiliyFominykh 4 месяца назад

@@inoyakaigor ))) Ещёб их различать )

@gatrianL 4 года назад

как отфильтровать массив объектов, если в объектах одинаковые значения ?

@frontendscience 4 года назад

Нужно написать свою функцию для метода array.filter, которая будет сравнивать значения внутри объектов ( так как сами объекты мы сравнить не сможем)

@kirillunlimited 4 года назад

По условию задачи сложность алгоритма должна быть O(1), а тут один проход массива - это ведь O(n). Или я не прав? Проясните, пожалуйста

@frontendscience 4 года назад

По условию сложность алгоритма ПО ПАМЯТИ должна быть O(1), а по времени сложность должна быть минимально возможная. В нашем случае это O(n)

@kirillunlimited 4 года назад

Спасибо!

@Алексей-б3ц6в 24 дня назад

ну хз, а если дубль в начале и вконце массива?

@Amerhannnシ 5 дней назад

массив уже отсортированный в задаче так написано

@romankotelnykov4405 Год назад

function removeDuplicates(arr) { let max = arr.length; for (let i = 0; i < max; i++) { if (arr[i] === arr[i + 1]) { continue; } arr[arr.length] = arr[i]; } arr = arr.splice(max); return arr.length; }

@AndrejVivat 3 года назад

Если такой вариант? const removeDupplicate = function(num) { for (let i = 0; i < num.length; i++) { while(num[i] == num[i+1]) { num.splice(i+1, 1) } } return num.length }

@frontendscience 3 года назад

да отлично!

@sergeyplotnikov5031 3 года назад

const removeDuplicates = arr => Object.keys(arr.reduce((acc, cur)=>({ ...acc, [cur]:null}))).length Как посчитать сложность моего варианта?

@frontendscience 3 года назад

По времени сложность линейная O(n). - reduce пройдется по всем элементам это линейная сложность - Object.keys тоже пройдется по всем элементам - в худшем случае это будет O(n) Значит результирующая сложность O(2n) что приводится просто к O(n)

@ІльченкоАртем 2 года назад

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

@frontendscience 2 года назад

Просто так не бывает, что без тренировок на чужих решениях кто-то берет и сходу пишет свое гениальное решение). Как раз такие разборы и тренируют думалку. Главное не бездумно их смотреть, а пытаться повторить алгоритм и запомнить его - чтоб когда встретится задача посложнее (в том числе и рабочая), вспомнить в нужный момент логику или взять нужную часть. Так нарабатывается опыт.

@МиколаГагін-э2с 4 года назад

Вариант если элементы массива идут не по порядку: codepen.io/nikww/pen/dyGwqbM ; жду комментарии и критику от всех) (изменено - читать комментарии снизу)

@frontendscience 4 года назад

Красиво! Единственный момент - я бы все таки использовал цикл через for - первый цикл (let i)должен пробежать от 0 до length-1 а второй всегда начинаться должен с i+1. При использовании forEach мы не можем задать начальный индекс - и выходит что второй цикл постоянно начинает бегать сначала.

@МиколаГагін-э2с 4 года назад

@@frontendscience я изменил код, так что-бы оставить forEach, думаю теперь багов не возникнет, но соглашусь что скорость роботы по сравнению с for меньше, так что выше я добавил вариант с for )

@antoncigur2724 2 года назад

Если я не смог понять как решить эту задачу-стоит ли дальше учит Js или просто фронтенд

@corvus278 2 года назад

Frontend считается довольно простым по сравнению с другими направлениями

@denisoleksyuk5346 3 года назад

как всегда по пробовал решить сам перед просмотром. ```js const input = [3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 6, 7, 8, 9, 9, 9] // 7 const removeDuplicates = (nums) => { for (let i = 0; i < nums.length; i++) { if (nums[i - 1] === nums[i]) { nums.splice(i, 1) i--; } } return nums.length; }; console.log(removeDuplicates(input)); ```

@frontendscience 3 года назад

Отлично! Благодарю!

@denisoleksyuk5346 3 года назад

@@frontendscience как продолжил, смотреть понял что решение идентично совпадает с вашим)

@ПавелЗайцев-я9у 4 года назад

return [...new Set(arr)]

@frontendscience 4 года назад

Да - выглядит очень заманчиво :) Для маленьких массивов думаю так и стоит делать. А вот на собеседованиях просят решить при очень больших массивах. Тут сложность по памяти уже играет роль сильно.

@bilionievgen9004 2 года назад

let removeDuplicates = function(nums) { let unique = nums.reduce((acc,num)=>{ acc[num] = acc[num] + 1 || 1; return acc; },{}) return Object.keys(unique).map(el=> +el) };

@rafomosinyan68 Год назад

var removeDuplicates = function(nums) { let k = 0; while(nums[k]!=="_"){ if(nums[k]!==nums[k+1]){ k++ }else{ nums.splice(k,1); nums.push("_") } } return k; };

@alexanderkosinskiy7339 2 года назад

const f = (arr) => arr.filter((item, index) => arr.indexOf(item) === index).length

@ВячеславФедотов-э9щ Год назад

@Cash5083 Год назад

Интересный вариант,но не берёт большие значения в отличие от сета.Попробуйте с таким массивом : [ 84827, 84827, 135765, 135765, 135765, 527149, 727615, 1444186, 1484845, 2681519, 2776574, 3831143, 3831143, 3831143, 3831143, 3976491, 3976491, 3976491, 3976491 ]