Чтобы удалить дубликаты на месте из отсортированного массива, я использую технику двух указателей: один указатель отслеживает текущий проверяемый элемент, а другой (insert_index) — позицию, куда нужно записать следующий уникальный элемент.
def remove_duplicates(arr):
if not arr:
return 0
insert_index = 1
for i in range(1, len(arr)):
if arr[i] != arr[i - 1]:
arr[insert_index] = arr[i]
insert_index += 1
return insert_index
insert_index начинается с 1, поскольку первый элемент всегда уникален1arr[insert_index]insert_index увеличивается на 1insert_index — количество уникальных элементовПоскольку массив уже отсортирован, все дубликаты стоят рядом друг с другом. Это означает, что достаточно просто сравнить arr[i] и arr[i - 1], чтобы обнаружить дубликат — никакого hash set или дополнительного поиска не нужно.
O(n) — массив обходится ровно один разO(1) — никаких дополнительных структур данных; все изменения вносятся на местеДля отсортированных массивов это решение оптимально — линейное время и константная память. Для неотсортированных массивов нужен другой подход (например, через set), но уже ценой O(n) дополнительной памяти.
Техника двух указателей в этом алгоритме использует один указатель для отслеживания текущего проверяемого элемента и другой указатель для отметки места, где должен быть размещён следующий уникальный элемент.
Новый — ещё не проверен сообществом
Вы