Два указателя: медленный и быстрый
Применяйте приём медленного и быстрого указателей для удаления дубликатов на месте, перемещения нулей и разделения массивов относительно опорного значения
«Два указателя: медленный и быстрый» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 4 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.
Медленный и быстрый указатели: объяснение
Шаблон медленного и быстрого указателей, также называемый методом черепахи и зайца, использует два указателя, которые движутся с разной скоростью по одной последовательности. В отличие от указателей, движущихся от противоположных концов, оба указателя начинают с начала. Медленный указатель перемещается на один шаг за раз, а быстрый — на два или больше. Разница в скорости создаёт полезные инварианты: медленный указатель отслеживает «корректный префикс», а быстрый просматривает последовательность дальше в поисках нужных условий.
# Slow pointer marks the write position;
# Fast pointer scans for next non-duplicate.
def remove_duplicates(nums):
if not nums: return 0
slow = 0 # next position to write a unique value
for fast in range(1, len(nums)):
if nums[fast] != nums[slow]:
slow += 1
nums[slow] = nums[fast]
return slow + 1 # new length
nums = [1, 1, 2, 3, 3, 3, 4]
k = remove_duplicates(nums)
print(nums[:k]) # [1, 2, 3, 4]Удаление дубликатов из отсортированного массива
В отсортированном массиве дубликаты расположены рядом. Медленный указатель отслеживает последнее записанное уникальное значение, а быстрый указатель просматривает элементы дальше. Когда быстрый указатель достигает значения, отличного от nums[slow], переместите медленный указатель и скопируйте новое значение. Этот алгоритм работает на месте за O(n) времени и использует O(1) дополнительной памяти — это стандартная задача на собеседованиях, проверяющая владение шаблоном указателей чтения и записи.
def remove_duplicates_v2(nums):
slow = 0
for fast in range(len(nums)):
if nums[fast] != nums[slow]:
slow += 1
nums[slow] = nums[fast]
return slow + 1
# Allow at most 2 occurrences
def remove_duplicates_k2(nums):
slow = 0
for fast in range(len(nums)):
if slow < 2 or nums[fast] != nums[slow - 2]:
nums[slow] = nums[fast]
slow += 1
return slow
print(remove_duplicates_k2([1,1,1,2,2,3]))
# Result: 5, nums[:5] = [1,1,2,2,3]Перемещение нулей с помощью медленного и быстрого указателей
Переместите все нули в конец, сохранив относительный порядок ненулевых элементов. Медленный указатель отмечает следующую позицию для ненулевого элемента. Быстрый указатель просматривает массив в поисках ненулевых значений. Когда быстрый указатель находит такое значение, скопируйте его в позицию медленного указателя и переместите оба указателя. После завершения прохода заполните нулями позиции от медленного указателя до конца массива. Время работы — O(n), дополнительная память — O(1).
def move_zeroes(nums):
slow = 0 # next position for a non-zero
for fast in range(len(nums)):
if nums[fast] != 0:
nums[slow] = nums[fast]
slow += 1
# Fill rest with zeroes
while slow < len(nums):
nums[slow] = 0
slow += 1
nums = [0, 1, 0, 3, 12]
move_zeroes(nums)
print(nums) # [1, 3, 12, 0, 0]Разбиение массива относительно опорного элемента
Шаг разбиения в быстрой сортировке перестраивает элементы на месте так, чтобы все значения < опорного элемента находились перед значениями >= опорного элемента. Схема Ломуто использует медленный указатель, отмечающий последнюю позицию небольшого элемента, и быстрый указатель, просматривающий элементы впереди. Когда быстрый указатель находит небольшой элемент, увеличьте значение медленного указателя и выполните обмен. Алгоритм работает за O(n) времени и использует O(1) дополнительной памяти.
def lomuto_partition(nums, low, high):
pivot = nums[high]
slow = low - 1 # last position of small element
for fast in range(low, high):
if nums[fast] <= pivot:
slow += 1
nums[slow], nums[fast] = nums[fast], nums[slow]
# Place pivot in final position
nums[slow+1], nums[high] = nums[high], nums[slow+1]
return slow + 1 # pivot's final index
arr = [3, 1, 4, 1, 5, 9, 2, 6]
p = lomuto_partition(arr, 0, len(arr)-1)
print(arr) # elements before p are <= pivotПоиск середины связного списка
При использовании медленного и быстрого указателей в связном списке быстрый указатель перемещается на два узла за шаг, а медленный — на один. Когда быстрый указатель достигает конца, медленный оказывается в середине. Этот однопроходный подход за O(n) гораздо проще, чем сначала подсчитывать узлы, а затем проходить половину списка. Он используется как отдельный шаг сортировки слиянием связных списков и обнаружения палиндромов в связном списке.
class Node:
def __init__(self, val, nxt=None):
self.val = val
self.next = nxt
def find_middle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow # slow is at middle
# Build 1->2->3->4->5
h = Node(1, Node(2, Node(3, Node(4, Node(5)))))
mid = find_middle(h)
print(mid.val) # 3 (middle of 5 nodes)Обнаружение цикла: черепаха и заяц Флойда
Алгоритм обнаружения циклов Флойда помещает медленный и быстрый указатели в начало связного списка. Медленный указатель перемещается на один узел, а быстрый — на два. Если цикл существует, быстрый указатель в конце концов обгонит медленный, и они встретятся внутри цикла. Если быстрый указатель достигает пустого значения, цикла нет. Встреча гарантирована, поскольку на каждой итерации быстрый указатель получает преимущество в один шаг: в цикле длины k указатели встретятся не позднее чем через k шагов после входа медленного указателя в цикл.
class ListNode:
def __init__(self, val=0, nxt=None):
self.val = val
self.next = nxt
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast: # identity check (same object)
return True
return False
# 1->2->3->4->2 (cycle at node 2)
n1 = ListNode(1)
n2 = ListNode(2)
n3 = ListNode(3)
n4 = ListNode(4)
n1.next=n2; n2.next=n3; n3.next=n4; n4.next=n2
print(has_cycle(n1)) # TrueПоиск точки входа в цикл
После обнаружения цикла, когда указатели совпали, верните один из них в начало списка. Затем перемещайте оба указателя по одному шагу за раз. Они встретятся в точке входа в цикл. Это основано на математическом свойстве: расстояние от начала списка до точки входа в цикл равно расстоянию от точки встречи до точки входа по модулю длины цикла. Это красивый математический результат, который часто встречается в сложных задачах на собеседованиях.
def detect_cycle(head):
slow = fast = head
# Phase 1: detect
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
break
else:
return None # no cycle
# Phase 2: find entry
slow = head
while slow is not fast:
slow = slow.next
fast = fast.next
return slow # cycle entry node
# Using same cycled list as previous scene
print(detect_cycle(n1).val) # 2 (cycle entry)Медленный и быстрый указатели для счастливого числа
Медленный и быстрый указатели применимы не только к связным спискам, но и к любому процессу, в котором возникают циклы. «Счастливое число» проходит через последовательность сумм квадратов цифр; если число не является счастливым, последовательность в конце концов зацикливается. Обнаружьте цикл с помощью медленного указателя, делающего один шаг, то есть вычисляющего один квадрат цифры, и быстрого указателя, делающего два шага. Если они встретились в 1, число счастливое; иначе оно оказалось в цикле, не содержащем 1. Это алгоритм Флойда, применённый к виртуальному связному списку значений.
def is_happy(n):
def next_val(x):
total = 0
while x:
x, d = divmod(x, 10)
total += d * d
return total
slow = n
fast = next_val(n)
while fast != 1 and slow != fast:
slow = next_val(slow)
fast = next_val(next_val(fast))
return fast == 1
print(is_happy(19)) # True (1->9->...->1)
print(is_happy(2)) # False (enters a cycle)N-й Node с конца списка
Найдите N-й узел с конца связного списка за один проход с помощью двух указателей. Переместите быстрый указатель на N шагов вперёд. Затем перемещайте оба указателя вместе, пока быстрый не достигнет конца: теперь медленный указатель находится на N-м узле с конца. Чтобы удалить этот узел, храните указатель на предыдущий узел, расположенный на один шаг позади медленного указателя. Это классическая однопроходная задача о связном списке, позволяющая не подсчитывать сначала его общую длину.
def remove_nth_from_end(head, n):
dummy = ListNode(0)
dummy.next = head
fast = slow = dummy
# Advance fast n+1 steps
for _ in range(n + 1):
fast = fast.next
# Advance together
while fast:
slow = slow.next
fast = fast.next
# slow.next is the nth from end
slow.next = slow.next.next
return dummy.next
# Build 1->2->3->4->5, remove 2nd from end
h2 = ListNode(1,ListNode(2,ListNode(3,ListNode(4,ListNode(5)))))
result = remove_nth_from_end(h2, 2)
# Should give 1->2->3->5Медленный и быстрый указатели в задачах со строками
Мышление в терминах медленного и быстрого указателей применимо также к задачам о массивах и строках. При сжатии строки с кодированием длин серий медленный указатель отмечает позицию записи, а быстрый просматривает элементы до конца каждой серии. Если все символы серии совпадают с символом в позиции записи, переместите быстрый указатель; в противном случае запишите сведения о серии и обновите медленный указатель. Это даёт O(n) за один проход при использовании O(1) дополнительной памяти.
def compress(chars):
slow = fast = 0
while fast < len(chars):
char = chars[fast]
count = 0
# Count the run
while fast < len(chars) and chars[fast] == char:
fast += 1
count += 1
chars[slow] = char
slow += 1
if count > 1:
for c in str(count):
chars[slow] = c
slow += 1
return slow
chars = list('aabcccccaa')
print(compress(chars)) # 6
print(chars[:6]) # ['a','2','b','c','5','a']... wait
# Actually: ['a','2','b','c','5','a','2']Выбор между медленным и быстрым указателями и указателями с противоположных концов
Используйте указатели с противоположных концов, когда задача связана с парами, сумма которых равна заданному значению, проверкой палиндрома или сужением окна с обеих сторон. Используйте медленный и быстрый указатели, когда нужен указатель записи для удаления или перемещения элементов, при обработке структуры связного списка — поиска середины или цикла, — либо при обнаружении циклов в любой последовательности значений. Оба подхода устраняют вложенные циклы и достигают O(n); решающим фактором является структура обхода.
# Pattern matcher:
# 1. Sorted array, target sum -> OPPOSITE ENDS
# 2. Remove/filter elements in-place -> SLOW-FAST (read-write)
# 3. Linked list middle/cycle -> SLOW-FAST (1x vs 2x speed)
# 4. Detect cycle in value sequence -> SLOW-FAST (Floyd)
# Example: given sorted array, remove val in-place
def remove_sorted(nums, val):
slow = 0
for fast in range(len(nums)):
if nums[fast] != val:
nums[slow] = nums[fast]
slow += 1
return slow
nums = [0,1,2,2,3,0,4,2]
print(remove_sorted(nums, 2)) # 5Быстрая проверка
Проверьте, насколько хорошо Вы поняли концепции структур данных и алгоритмов — подготовки к собеседованиям по программированию, рассмотренные в этом уроке.
Итоги урока
В этом уроке Вы узнали, что шаблон медленного и быстрого указателей, или чтения и записи, удерживает указатель записи на следующей допустимой позиции, пока быстрый указатель движется вперёд; это основа удаления, удаления дубликатов и перемещения нулей на месте, метод черепахи и зайца Флойда обнаруживает циклы за O(n) времени и использует O(1) памяти благодаря разнице в скоростях двух указателей, а после обнаружения цикла возврат одного указателя в начало и перемещение обоих с одинаковой скоростью позволяет найти точку входа в цикл благодаря доказуемому равенству расстояний. Далее мы рассмотрим строковый API Python для собеседований.
Часто задаваемые вопросы
Урок «Два указателя: медленный и быстрый» бесплатный?
Да — полный текст урока «Два указателя: медленный и быстрый» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Два указателя: медленный и быстрый»?
Применяйте приём медленного и быстрого указателей для удаления дубликатов на месте, перемещения нулей и разделения массивов относительно опорного значения Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 4 из 4.
Сколько времени занимает урок «Два указателя: медленный и быстрый»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Основы массивов и операции на месте
- Префиксные суммы и текущие итоги
- Два указателя: от противоположных концов
- Два указателя: медленный и быстрый