Раскройте возможности двухуказательных алгоритмов для оптимального решения распространенных задач с массивами

Введение

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

Техника двух указателей

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

Основная идея:

  1. Инициализация. Вы инициализируете два указателя, часто называемые left и right или i и j, на определенные позиции в массиве. Иногда они оба начинаются в начале, или один в начале, и один в конце, или в любой другой позиции в зависимости от решаемой проблемы.
  2. Перемещение. Указатели перемещаются при определенных условиях. Это может включать в себя перемещение их навстречу друг другу, удаление друг от друга или даже перемещение в одном направлении с разной скоростью.
  3. Проверка условий. На каждом этапе вы используете значения указателей, чтобы проверить какое-то условие или выполнить какое-то действие. Это могут быть такие вещи, как сравнение значений, на которые они указывают, или изменение элементов массива и т. д.
  4. Завершение. Алгоритм продолжается до тех пор, пока указатели не удовлетворят некоторому условию завершения. Это может быть, когда они пересекаются, достигают конца массива или находят нужный элемент и т. д.

Используя таким образом два указателя, вы часто можете уменьшить временную сложность алгоритмов и решить проблемы, которые в противном случае могли бы потребовать вложенных циклов.

Понимание двухуказателя на примере

Удалить дубликаты из отсортированного массива. Учитывая отсортированный массив nums, удалите дубликаты на месте так, чтобы каждый элемент появлялся только один раз, и верните новую длину. Вы должны сделать это, изменив входной массив на месте с дополнительной памятью O (1).

Input: nums = [1,1,2]
Output: length = 2, nums = [1,2]

Алгоритм:

Понимание ограничений проблемы.Во-первых, обратите внимание, что массив уже отсортирован. Это означает, что все повторяющиеся значения будут находиться рядом друг с другом.

Инициализация указателей.Начнем с двух указателей, назовем их i и j. Оба начинаются с начала массива.

Проверка обхода и условий.Мы используем i, чтобы отслеживать позицию, в которой должен быть помещен следующий уникальный элемент, и j, чтобы пройти по массиву и найти следующий уникальный элемент.

  • Если array[i] и array[j] совпадают, переместите j к следующему элементу (j++).
  • Если array[i] и array[j] различны, это означает, что array[j] — следующий уникальный элемент. Переместите его к последнему уникальному элементу (array[i+1] = array[j]), а затем переместите i и j на один вверх.

Вернуть длину:Наконец, i+1 будет длиной массива, содержащего только уникальные элементы. Мы возвращаем это значение.

Псевдокод

# Initialize two pointers i and j
i = 0  # to keep track of the position until which the array is free from duplicates.
j = 1  # to explore the rest of the array for unique elements.

# Loop through the array using j.
while j < len(array):
    # If the elements at i and j are the same, move j forward
    if array[i] == array[j]:
        j += 1
    else:
        # If the elements are different, move i one step forward
        i += 1
        # Copy the value from j to i
        array[i] = array[j]
        # Move j one step forward
        j += 1

# Return the length of the new array (i will be at the last unique element)
return i + 1

Java Решение вышеуказанной проблемы можно найти на Github.

Техника двух указателей особенно полезна в следующих сценариях:

  1. Сортированные массивы. Если у вас есть отсортированный массив и вы хотите найти пару элементов, соответствующих определенному условию. Например, поиск двух чисел в отсортированном массиве, сумма которых равна заданной цели.
  2. Проверка палиндрома. Если вам нужно проверить, является ли строка палиндромом, вы можете использовать два указателя, начиная с каждого конца и двигаясь к середине.
  3. Разделение массива. Для задач, требующих разделения массива на разделы, соответствующие определенным условиям. Например, разделение нулей и единиц в двоичном массиве.
  4. Три указателя. Иногда вариант с тремя указателями можно использовать для задач, в которых задействованы три массива или для выполнения условия требуется три элемента.

Распространенные проблемы, связанные с методом двух указателей (Leetcode)

  • Объединить отсортированный массив: вам даны два целочисленных массива nums1 и nums2, отсортированные в неубывающем порядке, и два целых числа m и n, представляющие количество элементов в nums1 и nums2 соответственно. Объедините nums1 и nums2 в один массив, отсортированный в неубывающем порядке.
  • Переместить нули: Учитывая целочисленный массив nums, переместите все 0 в его конец, сохраняя относительный порядок ненулевых элементов.
  • Поворот массива: Учитывая целочисленный массив nums, поверните массив вправо на k шагов, где k неотрицательное число.
  • Разбиение массива в соответствии с заданной опорной точкой: учитывая целочисленный массив nums с индексом 0 и целое число pivot, переставьте nums так, чтобы все элементы меньше pivot располагались перед элементами, равными pivot, которые, в свою очередь, предшествовали элементам больше pivot. Относительный порядок элементов меньше pivot и элементов больше pivot должен оставаться прежним. Верните переставленный nums.
  • 3Sum: Учитывая целочисленный массив чисел, вернуть все тройки [nums[i], nums[j], nums[k]], такие как i != j, i != k, j != k и nums[i] + nums[j] + nums[k] == 0.
  • Сортировка цветов. Учитывая массив nums с n объектами красного, белого или синего цвета, отсортируйте их по месту так, чтобы объекты одного цвета располагались рядом, а цвета располагались в определенном порядке. красный белый и синий.
  • Найти K-е наименьшее расстояние пары: расстояние пары целых чисел a и b определяется как абсолютная разница между a и b. Учитывая целочисленный массив nums и целое число k, верните kth наименьшее расстояние среди всех пар nums[i] и nums[j] где 0 <= i < j < nums.length.

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

Ссылки:

  • Некоторые проблемы и примеры в этой статье были адаптированы из LeetCode. Для получения более подробной информации посетите Веб-сайт LeetCode.

Примечание. По мере того, как я завершаю писать о различных проблемах со структурой данных и алгоритмами, соответствующие ссылки будут постоянно обновляться. Чтобы быть в курсе нового контента и обновлений, рассмотрите возможность добавления в закладки этой страницы или подписки на наши публикации.