Дано: из целочисленного отсортированного массива 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).
