Структуры - Алгоритмы - 26. Remove Duplicates from Sorted Array

Дано: из целочисленного отсортированного массива nums, удалить дубликаты.
Изменить массив nums таким образом, чтобы первые k элементов nums содержали уникальные элементы в том порядке, в котором они присутствовали в nums изначально. Остальные элементы nums не важны, так же как и размер nums. Вернуть k.

Ограничения:
1 <= nums.length <= 3 * 10^4
-100 <= nums[i] <= 100

Пример:

Вход: nums = [0,0,1,1,1,2,2,3,3,4].
Выходные данные: 5

Решение(Python):

1) Использование встроенной функции sorted и множества Set

def removeDuplicates(nums: List[int]) -> int:
nums[:] = sorted(set(nums))
return len(nums)

Чтобы получить новый массив создаем копию списка nums[:], либо другой вариант (nums.copy()) и сортируем, как множество уникальных элементов Set.

Временная сложность: sorted дает нам сложность O(nlog n)
Пространственная сложность: используем новый список - это O(n)

2) С использованием OrderedDict

OrderedDict это класс словаря, который сохраняет порядок, в котором пары ключ-значение, известные как элементы (items), были вставлены в словарь.

from collections import OrderedDict

def removeDuplicates(nums):
nums[:] = OrderedDict.fromkeys(nums)
return len(nums)

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

Временная сложность: sorted дает нам сложность O(nlog n)

Пространственная сложность: используем новый список - это O(n)

3) Использование указателей

def removeDuplicates(nums: List[int]) -> int:
slow, fast = 0, 1
while fast in range(len(nums)):
if nums[slow] == nums[fast]:
fast += 1
else:
nums[slow+1] = nums[fast]
fast += 1
slow += 1

return slow + 1

Использование двух указателей: медленно slow и быстрого fast Медленный указатель используется для "фиксации" уникального элемента, а быстрый - для продвижения по списку и поиска идентичных элементов в отсортированном массиву. быстрый указатель перебирает повторяющиеся элементы, и когда находит отличающийся элемент, заменяет им первый повторяющийся элемент. Затем мы перемещаем медленный указатель slow для фиксации этого нового числа на одну позицию, и начинаем перебор быстрым указателем с индекса, где он остановился предыдущий раз.

Улучшенный вариант:

def removeDuplicates(nums: List[int]) -> int:
slow = 1
for fast in range(1, len(nums)):
if nums[fast] != nums[fast - 1]:
nums[slow] = nums[fast]
slow += 1
return slow

Тот же принцип использования двух указателей, i и j, для итерации по массиву. Переменная j используется для отслеживания текущего индекса, в который должен быть помещен уникальный элемент. Начальное значение j равно 1, так как первый элемент массива всегда уникален и не нуждается в изменении. Если текущий элемент nums[i] не равен предыдущему элементу nums[i - 1], значит, мы встретили новый уникальный элемент. В этом случае мы обновляем nums[j] значением уникального элемента по адресу nums[i], а затем увеличиваем j на 1, чтобы отметить следующую позицию для нового уникального элемента.
Таким образом, мы перезаписываем все дубликаты в массиве и сохраняем только уникальные элементы. По окончании цикла значение j представляет собой длину результирующего массива с удаленными дубликатами.

Временная сложность: цикл дает нам сложность O(n)

Пространственная сложность: O(1).

4) Использование pop()

def removeDuplicates(nums: List[int]) -> int:
i = 1
while i < len(nums):
if nums[i] == nums[i - 1]:
nums.pop(i)
else:
i += 1
return len(nums)

Простой хороший вариант с использованием свойства pop(), удаление элемента по индексу. Проходим циклом, удаляем повторяющиеся элементы

Временная сложность: цикл дает нам сложность O(n)
Пространственная сложность: O(1).