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

Метод 1: подход двух указателей

Подход с двумя указателями — эффективный метод удаления дубликатов из отсортированного массива. Он использует два указателя: один для обхода массива, а другой для размещения неповторяющихся элементов.

def remove_duplicates(nums):
    if not nums:
        return 0
    i = 0  # pointer for placing non-duplicate elements
    for j in range(1, len(nums)):
        if nums[j] != nums[i]:
            i += 1
            nums[i] = nums[j]
    return i + 1

Объяснение: мы инициализируем указатель iзначением 0 и перебираем массив с указателем j, начиная с индекса 1. Если элемент с индексом jне равен элементу с индексом i, это означает, что мы нашли неповторяющийся элемент. Мы увеличиваем iи помещаем неповторяющийся элемент в обновленный индекс i. Наконец, мы возвращаем i + 1, который представляет длину обновленного массива.

Метод 2: использование структуры данных Python set

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

def remove_duplicates(nums):
    return len(set(nums))

Пояснение: Преобразуя массив в набор, мы автоматически удаляем все дубликаты. Затем мы возвращаем длину набора, которая представляет собой количество уникальных элементов.

Метод 3: использование itertools.groupby

Функция groupbyиз модуля Python itertoolsтакже может использоваться для удаления дубликатов из отсортированного массива.

from itertools import groupby
def remove_duplicates(nums):
    return len([k for k, _ in groupby(nums)])

Объяснение: Функция groupbyгруппирует последовательные элементы с одинаковым значением. Перебирая группы и извлекая уникальные ключи, мы можем получить количество уникальных элементов в массиве.

В этой статье мы рассмотрели три различных метода удаления дубликатов из отсортированного массива. Подход с двумя указателями является наиболее эффективным, поскольку он изменяет массив на месте. Однако, если порядок элементов не важен, использование структуры данных Python setили itertools.groupbyможет обеспечить краткое решение. Понимание этих методов поможет вам эффективно обрабатывать дубликаты в отсортированных массивах во время вашего пути к программированию.