Remove Duplicates from Sorted Array

Q: Как удалить дубликаты на месте без дополнительной памяти?

Держите индекс записи k рядом с индексом чтения. Первые k ячеек содержат уникальные значения, найденные к этому моменту. Если прочитанное значение отличается от nums[k-1] , скопируйте его в nums[k] и увеличьте k . Индекс записи никогда не обгоняет индекс чтения, поэтому ничего не перезаписывается до того, как будет прочитано.

ЛегкоДва указателя

+10

Дан массив целых чисел nums, отсортированный в неубывающем порядке, поэтому одинаковые значения располагаются рядом. Верните различные значения nums — каждое по одному разу, в порядке их появления. Например, [2, 2, 5] дает [2, 5].

Функция

removeDuplicates(nums: integer-array) → integer-array

numsinteger-array: целые числа, отсортированные в порядке неубывания
Возвращаетinteger-array: уникальные значения nums в порядке возрастания

Ограничения

1 ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
Массив nums отсортирован в неубывающем порядке.

Примеры

Ввод: nums = [1, 1, 2, 3, 3, 3]
Вывод: [1, 2, 3]
Пояснение: 1 встречается дважды, а 3 — три раза. Если оставить по одному экземпляру каждого числа, получится [1, 2, 3].

Ввод: nums = [-2, 0, 0, 5]
Вывод: [-2, 0, 5]
Пояснение: Повторяется только 0. Отрицательные значения работают так же, поэтому ответ — [-2, 0, 5].

Ввод: nums = [7, 7, 7]
Вывод: [7]
Пояснение: Каждое значение — это 7, поэтому осталась только одна 7.

+15 скрытых тестов при отправке

Дополнительный вопрос

Можешь сделать это с использованием O(1) дополнительной памяти, изменяя nums на месте вместо создания второго массива?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

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

Запоминайте просмотренные значения в хеш-множестве

Идея

Пройдите по nums и храните множество значений, которые вы уже добавили в ответ. Если значения нет в множестве, добавьте его в ответ и в множество; если оно там есть — пропустите. Для [1, 1, 2, 3, 3, 3] ответ сначала становится [1], затем [1, 2], затем [1, 2, 3], а все последующие копии пропускаются.

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

В среднем поиск в множестве занимает O(1), поэтому проход выполняется за время O(n), но и множество, и ответ могут содержать по n значений: дополнительная память O(n). В C, где нет встроенного множества, ту же задачу решает массив флагов для 2 × 10^4 + 1 возможных значений.

Алгоритм

Создай пустое множество seen и пустой список result.
Для каждого значения в nums проверь, содержится ли оно в seen.
Если нет, добавь его в seen и добавь в конец result.
Верни result.

def removeDuplicates(nums):
    seen = set()
    result = []
    for num in nums:
        if num not in seen:
            seen.add(num)
            result.append(num)
    return result

Уплотнение на месте с помощью указателя записи

Идея

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

Используй два индекса. Индекс чтения i проходит по каждому значению. Индекс записи k отмечает конец сохранённой части: в диапазоне от nums[0] до nums[k-1] всегда находятся различные значения, найденные к этому моменту. Начни с k = 1, поскольку первое значение всегда сохраняется. Если nums[i] отличается от nums[k-1], скопируй его в nums[k] и увеличь k.

Для массива [1, 1, 2, 3, 3, 3]: при i = 1 читается вторая 1, и ничего не происходит. При i = 2 читается 2, которое отличается от nums[0] = 1, поэтому оно записывается по индексу 1, а k становится равным 2. При i = 3 значение 3 записывается по индексу 2, а k становится равным 3. Последние две 3 совпадают с nums[2] и пропускаются. Теперь в первых трёх ячейках находятся значения [1, 2, 3].

Индекс записи никогда не обгоняет индекс чтения, поскольку k всегда меньше или равен i, поэтому значение никогда не перезаписывается до того, как будет прочитано. Один проход занимает O(n) времени, а помимо возвращаемых значений используются два целых числа: дополнительная память O(1).

Алгоритм

Установи k = 1: nums[0] всегда сохраняется.
Перебирай i от 1 до последнего индекса.
Если nums[i] отличается от nums[k-1], установи nums[k] = nums[i] и увеличь k на 1.
Верни первые k значений nums.

def removeDuplicates(nums):
    # nums[0:k] holds the distinct values found so far, in order.
    k = 1
    for i in range(1, len(nums)):
        if nums[i] != nums[k - 1]:
            nums[k] = nums[i]
            k += 1
    return nums[:k]

Ловушки и крайние случаи

Код для указателя записи короткий, а ошибки связаны с тем, с каким значением вы сравниваете.

Сравнение nums[i] с nums[i+1], пока i доходит до последнего индекса. При последнем сравнении происходит чтение за пределами массива.
Начало с k, равного 0. Тогда первое значение сравнивается с nums[-1], которое находится вне диапазона или, в Python, является последним элементом.
Возврат всего массива вместо первых k значений. В хвосте остаются старые значения, поэтому [1, 1, 2] вернётся как [1, 2, 2].
Построение ответа перебором хеш-множества. В большинстве языков хеш-множество не сохраняет порядок, поэтому значения могут перемешаться; вместо этого добавляйте каждое значение в список при первой встрече.
В Lua и R массивы начинаются с 1. Сохраняемая часть — это nums[1]–nums[k], а сравнение выполняется с nums[k], а не с nums[k-1].

Частые вопросы4

Какова временная сложность алгоритма удаления дубликатов из отсортированного массива?

Решение с указателем записи считывает каждое значение один раз, поэтому работает за время O(n). Помимо возвращаемых значений, оно использует O(1) дополнительной памяти: два индекса.

Почему массив нужно отсортировать?

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

Как удалить дубликаты на месте без дополнительной памяти?

Держите индекс записи k рядом с индексом чтения. Первые k ячеек содержат уникальные значения, найденные к этому моменту. Если прочитанное значение отличается от nums[k-1], скопируйте его в nums[k] и увеличьте k. Индекс записи никогда не обгоняет индекс чтения, поэтому ничего не перезаписывается до того, как будет прочитано.

Как разрешить использовать каждое значение не более двух раз?

Сравнивай со значением на две позиции назад в сохранённой части, а не на одну: копируй nums[i], когда k < 2 или когда оно отличается от nums[k-2]. Если оно равно nums[k-2], значит, сохранённая часть уже заканчивается двумя его копиями. Та же идея позволяет оставить не более m копий, используя nums[k-m].

Python

def removeDuplicates(nums):
    # Напишите код здесь

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

nums = [1, 1, 2, 3, 3, 3]

Ожидается

[1, 2, 3]