Раскройте возможности двухуказательных алгоритмов для оптимального решения распространенных задач с массивами
Введение
Массивы являются краеугольным камнем структуры данных в информатике. Среди различных подходов к решению задач с массивами метод двух указателей выделяется как часто встречающийся и эффективный шаблон. Эта статья призвана дать вам всестороннее представление о пользе метода двух указателей для оптимизации и улучшения решений типичных проблем с массивами. Мы шаг за шагом проведем вас через основные принципы, проиллюстрируем их реальную полезность на примере задачи и дополним тщательно подобранным списком упражнений, которые помогут отточить ваши навыки.
Техника двух указателей
Техника двух указателей — это полезная стратегия для более эффективного решения различных задач, связанных с массивами. По сути, это предполагает использование двух указателей (или индексов) для перемещения по массиву, часто каждый из которых движется с разной скоростью или в исходной позиции. Это позволяет собирать информацию или вносить изменения по ходу работы за один проход по массиву, тем самым сокращая временную сложность.
Основная идея:
- Инициализация. Вы инициализируете два указателя, часто называемые
left
иright
илиi
иj
, на определенные позиции в массиве. Иногда они оба начинаются в начале, или один в начале, и один в конце, или в любой другой позиции в зависимости от решаемой проблемы. - Перемещение. Указатели перемещаются при определенных условиях. Это может включать в себя перемещение их навстречу друг другу, удаление друг от друга или даже перемещение в одном направлении с разной скоростью.
- Проверка условий. На каждом этапе вы используете значения указателей, чтобы проверить какое-то условие или выполнить какое-то действие. Это могут быть такие вещи, как сравнение значений, на которые они указывают, или изменение элементов массива и т. д.
- Завершение. Алгоритм продолжается до тех пор, пока указатели не удовлетворят некоторому условию завершения. Это может быть, когда они пересекаются, достигают конца массива или находят нужный элемент и т. д.
Используя таким образом два указателя, вы часто можете уменьшить временную сложность алгоритмов и решить проблемы, которые в противном случае могли бы потребовать вложенных циклов.
Понимание двухуказателя на примере
Удалить дубликаты из отсортированного массива. Учитывая отсортированный массив 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.
Техника двух указателей особенно полезна в следующих сценариях:
- Сортированные массивы. Если у вас есть отсортированный массив и вы хотите найти пару элементов, соответствующих определенному условию. Например, поиск двух чисел в отсортированном массиве, сумма которых равна заданной цели.
- Проверка палиндрома. Если вам нужно проверить, является ли строка палиндромом, вы можете использовать два указателя, начиная с каждого конца и двигаясь к середине.
- Разделение массива. Для задач, требующих разделения массива на разделы, соответствующие определенным условиям. Например, разделение нулей и единиц в двоичном массиве.
- Три указателя. Иногда вариант с тремя указателями можно использовать для задач, в которых задействованы три массива или для выполнения условия требуется три элемента.
Распространенные проблемы, связанные с методом двух указателей (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.
Примечание. По мере того, как я завершаю писать о различных проблемах со структурой данных и алгоритмами, соответствующие ссылки будут постоянно обновляться. Чтобы быть в курсе нового контента и обновлений, рассмотрите возможность добавления в закладки этой страницы или подписки на наши публикации.