JavaScript: удаление дубликатов из отсортированного массива на месте

Задача выбрана из списка самых популярных вопросов на собеседовании LeetCode

Сегодня мы будем работать над алгоритмом Удалить дубликаты из отсортированного массива из Списка самых популярных вопросов на собеседовании LeetCode:

Для отсортированного массива числа удалите дубликаты на месте, чтобы каждый элемент появлялся только один раз и возвращал новую длину.

Не выделяйте дополнительное пространство для другого массива, вы должны сделать это, изменив входной массив на месте, добавив O (1) дополнительной памяти.

Example 1:
Given nums = [1,1,2],
Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.
It doesn't matter what you leave beyond the returned length.
Example 2:
Given nums = [0,0,1,1,1,2,2,3,3,4],
Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.
It doesn't matter what values are set beyond the returned length.

В JavaScript существует несколько способов удаления дубликатов из массива. Использование встроенных методов может быть простым вариантом, но мы выберем более эффективный подход, который поможет нам легко работать с большими массивами. Мы удалим дубликаты на месте, изменив исходный массив. Чтобы решить эту проблему, мы будем использовать метод с двумя указателями: первый указатель (j) необходим для итерации по данному массиву, а второй указатель (i) необходим для размещения уникального числа в позиции рядом с ним.

Вот визуальное представление этого подхода:

Запишем шаги для решения этой проблемы:

1. Вернуть 0, если данный массив пуст.
2. Объявите два указателя i и j и установите для них значения 0 и 1 соответственно.
3. Используйте цикл while, чтобы проверить, совпадает ли число с индексом j с номером с индексом i.
4. Если нет, увеличьте i на 1 и скопируйте значение числа с индексом j в элемент с индексом i, а затем увеличьте j на 1.
5. Если они равны, увеличьте j, чтобы пропустить дубликат.
6. После завершения цикла верните длину уникальных чисел, равную i + 1.

Вот приведенная выше логика, реализованная в JavaScript:

Сначала мы заботимся о граничном случае пустого массива и возвращаем 0. Затем мы используем два указателя, чтобы упорядочить уникальные числа. Поскольку входной массив отсортирован, все повторяющиеся числа будут сгруппированы вместе. Мы могли определить новый массив и поместить туда уникальные элементы, но нас попросили изменить данный массив на месте с пространственной сложностью O (1). Мы сохраним два указателя; один указатель (j) перебирает все элементы в исходном массиве, а другой указатель (i) помещает новый не повторяющийся элемент.

Каждый раз, когда мы встречаем повторяющийся элемент, мы перемещаем j к следующему не повторяющемуся элементу. Когда мы видим уникальный элемент, мы переназначаем его на позицию рядом с последним не повторяющимся числом, с которым мы столкнулись. Этот процесс не удаляет дубликаты в исходном массиве, он просто перемещает уникальные числа в левую / переднюю часть массива. Мы повторяем тот же процесс, пока цикл не завершится, а затем функция вернет длину неповторяющихся чисел. Обратите внимание, что указатель i отслеживает последний уникальный элемент в массиве.

Сложность:

Временная сложность вышеуказанного алгоритма равна O (n), потому что мы выполняем итерацию по входному массиву только один раз, а n - это общее количество элементы в этом массиве. Алгоритм работает в постоянном пространстве; O (1), потому что мы не используем лишнее пространство.

Я надеюсь, что объяснения в этой статье будут полезны для понимания решения этого часто задаваемого вопроса на собеседовании. Спасибо за чтение и не стесняйтесь проверять мои другие статьи, написанные о разных алгоритмах: