Циклическая сортировка: пропущенные и повторяющиеся числа за O(n) и O(1) памяти

Паттерн cyclic sort для массивов с числами от 1 до n: как найти пропущенное и повторяющееся число, решить First Missing Positive за O(n) и O(1) памяти. Ловушки и код на Python.

9 мин чтенияалгоритмы · массивы · сортировка · python

Коротко

Если в массиве длины nn лежат числа из диапазона 1..n1..n (или 0..n0..n), то у каждого числа есть «родной» индекс: число v должно стоять на позиции v - 1. Циклическая сортировка расставляет числа по своим местам обменами, а потом одним проходом находит, где порядок нарушен. Там и спрятан ответ.

ЧтоЗначение
ВремяO(n)O(n): не больше n−1n - 1 обменов плюс nn шагов указателя
ПамятьO(1)O(1), массив меняется на месте
Когда применятьзначения ограничены длиной массива: 1..n1..n, 0..n0..n, «положительные до n»
Главная идеязначение — это адрес: nums[i] должно лежать в nums[nums[i] - 1]
Типичные задачиMissing Number, Find All Duplicates, Set Mismatch, First Missing Positive
Главная ловушкаусловие обмена и порядок присваивания в a, b = b, a

Если в условии звучит «числа от 1 до n» и «без дополнительной памяти», почти наверняка от вас ждут именно этот приём или его родственника — пометку знаком.

Интуиция: у каждого числа есть свой стул

Представьте nn стульев с номерами от 1 до nn и nn человек с билетами на эти же номера. Все сели как попало. Как рассадить их правильно, не выводя никого в коридор?

Подходим к первому стулу. На нём сидит человек с билетом №3. Пересаживаем его на стул №3, а того, кто сидел там, — на первый. Если и новый сосед не на своём месте, повторяем. Каждая пересадка ставит хотя бы одного человека на его законный стул, и больше его никто не трогает. Значит, пересадок будет не больше nn.

Почему «циклическая»? Любая перестановка раскладывается на циклы: 1 → 3 → 5 → 1 и так далее. Обмены на одной позиции прокручивают ровно один такой цикл, пока он не замкнётся.

Наивные решения и почему их мало

Задача: в массиве лежат различные числа от 1 до nn, расставьте их по порядку. Или классика попроще: найдите пропущенное число.

Первое, что приходит в голову:

  • Отсортировать и пройтись. O(nlog⁡n)O(n \log n) по времени, информацию о диапазоне мы просто выбросили.
  • Множество или массив флагов. O(n)O(n) по времени, но и O(n)O(n) памяти. Про устройство множеств — в статье про хеш-таблицы.
  • Сортировка подсчётом. Тоже линейна, но требует отдельного массива счётчиков: см. сортировку подсчётом.

Всё это нормальные ответы для разминки, и с них стоит начать на собеседовании. Но как только интервьюер добавляет «а за O(1)O(1) памяти?», нужно вспомнить, что сам массив и есть тот самый массив флагов. Индексы уже есть, их надо только использовать.

Базовый алгоритм

def cyclic_sort(nums): i = 0 while i < len(nums): j = nums[i] - 1 # куда должно попасть nums[i] if nums[i] != nums[j]: nums[i], nums[j] = nums[j], nums[i] else: i += 1 return nums print(cyclic_sort([3, 1, 5, 4, 2])) # [1, 2, 3, 4, 5]

Обратите внимание на две детали.

  1. После обмена указатель i не двигается. На позицию i пришло новое число, и его тоже надо проверить.
  2. Условие — nums[i] != nums[j], а не nums[i] != i + 1. Для массива без повторов это одно и то же, но как только появятся дубликаты, второй вариант зациклится. Об этом подробнее в разделе про ошибки.

Разбор на примере

Возьмём [3, 1, 5, 4, 2]:

ШагiМассивДействие
10[3, 1, 5, 4, 2]3 должно стоять на индексе 2 → обмен
20[5, 1, 3, 4, 2]5 → индекс 4 → обмен
30[2, 1, 3, 4, 5]2 → индекс 1 → обмен
40[1, 2, 3, 4, 5]1 на месте → i += 1
5–81–4[1, 2, 3, 4, 5]все на месте, указатель доходит до конца

Три обмена на позиции 0 прокрутили цикл 1 → 3 → 5 → 2 → 1. Число 4 с самого начала было в цикле длины 1 и не двигалось.

Почему это O(n)O(n), хотя внутри while есть «скрытый цикл»

Частый вопрос на собеседовании: «У вас указатель может стоять на месте много итераций подряд. Это точно не O(n2)O(n^2)?»

Аргумент такой. Каждая итерация цикла делает одно из двух:

  • обмен — после него число nums[j] стоит на своём месте и больше никогда не сдвинется, потому что мы трогаем только позиции, где число чужое. Таких событий не больше nn;
  • сдвиг i += 1 — их ровно nn.

Итого не больше 2n2n итераций. Это амортизированная оценка: тот же приём, что в монотонном стеке, где элемент кладут и вынимают не больше одного раза. Подробнее про такие рассуждения — в статье про O-нотацию.

Шаблон: расставь, потом найди нарушение

Почти все задачи паттерна решаются в две фазы:

  1. Расставить числа по местам, пропуская те, у которых нет места (ноль, отрицательные, больше nn) или место уже занято таким же числом.
  2. Пройтись по массиву: позиция i, где nums[i] != i + 1, — это и есть аномалия. Индекс говорит, какого числа не хватает (i + 1), а значение — какое число лишнее (nums[i]).

Дальше меняется только то, что именно мы возвращаем.

Missing Number: одно пропущенное из 0..n

LeetCode 268. Даны nn различных чисел из диапазона 0..n0..n, одного не хватает. Здесь число v хочет стоять на индексе v, а для числа nn места нет — его пропускаем.

def missing_number(nums): n = len(nums) i = 0 while i < n: j = nums[i] if j < n and nums[i] != nums[j]: nums[i], nums[j] = nums[j], nums[i] else: i += 1 for i in range(n): if nums[i] != i: return i return n print(missing_number([3, 0, 1])) # 2 print(missing_number([9, 6, 4, 2, 3, 5, 7, 0, 1])) # 8 print(missing_number([0, 1])) # 2

Честно скажу: для этой конкретной задачи есть решения изящнее и без порчи входа — сумма арифметической прогрессии и XOR индексов со значениями. Оба разобраны в статье про Single Number. Циклическая сортировка здесь полезна как тренировка: дальше начнутся задачи, где сумма и XOR уже не спасают.

Find All Numbers Disappeared: все пропущенные

LeetCode 448. Массив длины nn, числа от 1 до nn, некоторые встречаются дважды, некоторые — ни разу. Верните все пропущенные.

Сумма тут не поможет: пропущенных может быть несколько. А шаблон работает без изменений: дубликат просто останется на чужом месте, когда его «родной» стул уже занят таким же числом.

def find_disappeared_numbers(nums): i = 0 while i < len(nums): j = nums[i] - 1 if nums[i] != nums[j]: nums[i], nums[j] = nums[j], nums[i] else: i += 1 return [i + 1 for i in range(len(nums)) if nums[i] != i + 1] print(find_disappeared_numbers([4, 3, 2, 7, 8, 2, 3, 1])) # [5, 6]

После первой фазы массив выглядит так: [1, 2, 3, 4, 3, 2, 7, 8]. На позициях 4 и 5 стоят «лишние» тройка и двойка, а значит, не хватает чисел 5 и 6.

Find All Duplicates: все повторяющиеся

LeetCode 442. Те же условия, но каждое число встречается один или два раза, верните все дубли. Это та же картинка, что и в предыдущей задаче, только читаем не индекс, а значение:

def find_duplicates(nums): i = 0 while i < len(nums): j = nums[i] - 1 if nums[i] != nums[j]: nums[i], nums[j] = nums[j], nums[i] else: i += 1 return [nums[i] for i in range(len(nums)) if nums[i] != i + 1] print(find_duplicates([4, 3, 2, 7, 8, 2, 3, 1])) # [3, 2]

Задача «есть ли в массиве дубликаты вообще» в общем виде решается множеством: см. Contains Duplicate. Но если значения ограничены длиной массива, тот же вопрос закрывается циклической сортировкой без дополнительной памяти.

Set Mismatch: одно потерялось, другое задвоилось

LeetCode 645. В массиве должны были быть числа от 1 до nn, но одно из них заменили копией другого. Верните [дубликат, пропущенное].

Здесь видно, зачем шаблон держит обе половины информации. На «сломанной» позиции значение — дубликат, а индекс + 1 — пропущенное:

def find_error_nums(nums): i = 0 while i < len(nums): j = nums[i] - 1 if nums[i] != nums[j]: nums[i], nums[j] = nums[j], nums[i] else: i += 1 for i in range(len(nums)): if nums[i] != i + 1: return [nums[i], i + 1] print(find_error_nums([1, 2, 2, 4])) # [2, 3] print(find_error_nums([3, 2, 3, 4, 6, 5])) # [3, 1]

Find the Duplicate Number: когда массив трогать нельзя

LeetCode 287. Массив длины n+1n + 1, числа от 1 до nn, ровно одно число повторяется (возможно, много раз). Найдите его.

Циклическая сортировка даёт ответ даже раньше конца: как только хотим поставить число на место, а там уже такое же, — это дубликат.

def find_duplicate(nums): i = 0 while i < len(nums): if nums[i] != i + 1: j = nums[i] - 1 if nums[i] != nums[j]: nums[i], nums[j] = nums[j], nums[i] else: return nums[i] else: i += 1 return -1 print(find_duplicate([1, 3, 4, 2, 2])) # 2 print(find_duplicate([3, 1, 3, 4, 2])) # 3

Но в условии LeetCode 287 есть оговорка: массив изменять нельзя. Тогда циклическая сортировка не подходит, и в ход идёт другой взгляд на ту же идею «значение — это адрес». Если считать nums[i] указателем на следующий узел, массив превращается в связный список, а дубликат — в точку входа в цикл. Дальше работает алгоритм Флойда «черепаха и заяц», подробно разобранный в статье про цикл в связном списке:

def find_duplicate_floyd(nums): slow = fast = nums[0] while True: slow = nums[slow] fast = nums[nums[fast]] if slow == fast: break slow = nums[0] while slow != fast: slow = nums[slow] fast = nums[fast] return slow print(find_duplicate_floyd([1, 3, 4, 2, 2])) # 2

На собеседовании хорошо назвать оба варианта и спросить, можно ли портить вход. Само уточнение — уже плюс.

First Missing Positive: главная задача паттерна

LeetCode 41, уровень Hard. Дан произвольный массив целых чисел — с нулями, отрицательными, огромными значениями и повторами. Найдите наименьшее положительное число, которого в нём нет. Ограничения: O(n)O(n) по времени и O(1)O(1) дополнительной памяти.

Ключевое наблюдение

Ответ всегда лежит в диапазоне 1..n+11..n+1. Почему: в массиве nn ячеек, поэтому числа 1,2,…,n1, 2, \dots, n в лучшем случае все присутствуют, и тогда ответ n+1n + 1. Если хотя бы одного не хватает, ответ меньше.

Отсюда вывод: всё, что ≤0\le 0 или >n> n, на ответ не влияет. Такие числа можно просто оставить где лежат. Всё остальное — расставить циклической сортировкой.

def first_missing_positive(nums): n = len(nums) i = 0 while i < n: j = nums[i] - 1 if 0 <= j < n and nums[i] != nums[j]: nums[i], nums[j] = nums[j], nums[i] else: i += 1 for i in range(n): if nums[i] != i + 1: return i + 1 return n + 1 print(first_missing_positive([1, 2, 0])) # 3 print(first_missing_positive([3, 4, -1, 1])) # 2 print(first_missing_positive([7, 8, 9, 11, 12])) # 1

Проверка 0 <= j < n здесь обязательна. Без неё отрицательное j в Python молча обратится к элементу с конца массива, а в Java или JavaScript вы получите исключение или undefined.

Разберём [3, 4, -1, 1]:

ШагiМассивДействие
10[3, 4, -1, 1]3 → индекс 2, обмен
20[-1, 4, 3, 1]−1 вне диапазона, i += 1
31[-1, 4, 3, 1]4 → индекс 3, обмен
41[-1, 1, 3, 4]1 → индекс 0, обмен
51[1, -1, 3, 4]−1 вне диапазона, i += 1
6–72–3[1, -1, 3, 4]3 и 4 на месте

Второй проход: на индексе 1 стоит −1 вместо 2. Ответ — 2.

То же на JavaScript

Тот же код на JavaScript почти не отличается. Индекс j вычисляем заранее — почему это важно, расскажу ниже.

function firstMissingPositive(nums) { const n = nums.length let i = 0 while (i < n) { const j = nums[i] - 1 if (j >= 0 && j < n && nums[i] !== nums[j]) { ;[nums[i], nums[j]] = [nums[j], nums[i]] } else { i++ } } for (let k = 0; k < n; k++) { if (nums[k] !== k + 1) return k + 1 } return n + 1 } console.log(firstMissingPositive([3, 4, -1, 1])) // 2

Альтернатива: пометка знаком

Тот же эффект «массив как таблица флагов» можно получить без обменов. Сначала заменяем всё, что вне 1..n1..n, на n+1n + 1. Затем для каждого значения v делаем элемент nums[v - 1] отрицательным — это флаг «число v встречалось». Первая положительная позиция и даёт ответ.

def first_missing_positive_sign(nums): n = len(nums) for i in range(n): if nums[i] <= 0 or nums[i] > n: nums[i] = n + 1 for i in range(n): v = abs(nums[i]) if v <= n: nums[v - 1] = -abs(nums[v - 1]) for i in range(n): if nums[i] > 0: return i + 1 return n + 1 print(first_missing_positive_sign([3, 4, -1, 1])) # 2

Какой вариант выбрать? Пометка знаком делает три простых прохода без хитрого while, её проще доказать. Циклическая сортировка универсальнее: тот же каркас решает все задачи выше, а после неё массив ещё и частично упорядочен. Оба варианта меняют входной массив, и об этом стоит сказать вслух.

Типичные ошибки

1. Порядок присваивания в Python-обмене

Самая коварная ошибка, на которой спотыкаются даже опытные разработчики. Хочется написать обмен в одну строку, без промежуточной переменной:

nums[i], nums[nums[i] - 1] = nums[nums[i] - 1], nums[i] # так нельзя

Правая часть вычисляется целиком и правильно. А вот присваивания слева выполняются по очереди, слева направо. Сначала в nums[i] записывается новое значение, и только потом вычисляется индекс nums[i] - 1 — уже по новому nums[i]. Второе присваивание попадает не туда.

Проверьте сами: для [2, 1] такая строка оставляет массив [2, 1] без изменений, и while крутится бесконечно. В JavaScript деструктуризация [a[i], a[a[i] - 1]] = [a[a[i] - 1], a[i]] ведёт себя точно так же.

Лечение — вычислить индекс заранее в переменную j, как во всех примерах выше. Работает и перестановка целей местами (nums[nums[i] - 1], nums[i] = ...), но на это полагаться не стоит: код, корректность которого зависит от порядка присваивания, легко сломать при следующей правке.

2. Условие nums[i] != i + 1 вместо nums[i] != nums[j]

Для массива с дубликатами вроде [3, 1, 2, 2] первое условие говорит «двойка на индексе 3 не на месте», и мы меняем её с двойкой на индексе 1. Массив не меняется, указатель не двигается — бесконечный цикл. Сравнивать нужно с тем, что лежит на целевой позиции: если там уже такое же число, обмен бессмыслен, идём дальше.

3. Сдвиг указателя после обмена

Если писать for i in range(n) с одним обменом внутри, на позицию i придёт новое число, которое так и останется не на своём месте. Нужен либо while с ручным i += 1 только в ветке «на месте», либо вложенный while внутри for.

4. Забыли про числа вне диапазона

Ноль, отрицательные и числа больше nn надо явно пропускать. В Python отрицательный индекс не упадёт, а тихо выдаст неверный ответ — это хуже исключения.

5. Смещение на единицу

Для диапазона 1..n1..n число v стоит на индексе v - 1, для 0..n0..n — на индексе v. Перед кодом проговорите, какой у вас диапазон, и проверьте граничные случаи: пустой массив, один элемент, пропущено самое большое число.

6. Испорченный вход без предупреждения

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

Когда паттерн не подходит

  • Значения не ограничены длиной массива. Если числа произвольные, «родного» индекса нет. Нужна хеш-таблица или сортировка.
  • Вход менять нельзя. Тогда смотрите на сумму, XOR, Флойда или бинарный поиск по ответу (для задачи 287 он даёт O(nlog⁡n)O(n \log n) без модификации; см. бинарный поиск по ответу).
  • Нужен стабильный порядок или исходные позиции. Циклическая сортировка их уничтожает.

Где встречается на собеседованиях

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

  • First Missing Positive — любимая Hard-задача из-за жёсткого ограничения по памяти. Интервьюер ждёт наблюдения «ответ в 1..n+11..n+1» — это половина решения.
  • Find the Duplicate Number — проверка, знаете ли вы и обмены, и Флойда, и умеете ли уточнить, можно ли менять вход.
  • Find All Duplicates / Disappeared Numbers — на разминке или как follow-up после варианта с множеством: «а теперь без дополнительной памяти».
  • Missing Number — простой вход в тему, где хорошо показать три решения (сумма, XOR, обмены) и сравнить их.

Как узнать задачу в незнакомой формулировке: ищите в условии «числа от 1 до n», «длина массива n», «найти пропущенное или лишнее» и «O(1)O(1) памяти». Если всё это есть, первым делом спросите себя: можно ли поставить каждое число на индекс, равный ему самому?

Итог

  • Число v из диапазона 1..n1..n имеет естественное место — индекс v - 1. Массив можно использовать как свою же таблицу флагов.
  • Две фазы: расставить обменами, затем найти позиции, где nums[i] != i + 1.
  • Время O(n)O(n): каждый обмен навсегда ставит одно число на место. Память O(1)O(1).
  • Сравнивайте с целевой ячейкой (nums[i] != nums[j]), вычисляйте j заранее и пропускайте числа вне диапазона.
  • Если вход трогать нельзя — переходите на сумму, XOR или алгоритм Флойда.

Потренироваться в спокойной обстановке

Все задачи