Циклическая сортировка: пропущенные и повторяющиеся числа за O(n) и O(1) памяти
Паттерн cyclic sort для массивов с числами от 1 до n: как найти пропущенное и повторяющееся число, решить First Missing Positive за O(n) и O(1) памяти. Ловушки и код на Python.
Коротко
Если в массиве длины лежат числа из диапазона (или ), то у каждого числа есть «родной» индекс: число v должно стоять на позиции v - 1. Циклическая сортировка расставляет числа по своим местам обменами, а потом одним проходом находит, где порядок нарушен. Там и спрятан ответ.
| Что | Значение |
|---|---|
| Время | : не больше обменов плюс шагов указателя |
| Память | , массив меняется на месте |
| Когда применять | значения ограничены длиной массива: , , «положительные до n» |
| Главная идея | значение — это адрес: nums[i] должно лежать в nums[nums[i] - 1] |
| Типичные задачи | Missing Number, Find All Duplicates, Set Mismatch, First Missing Positive |
| Главная ловушка | условие обмена и порядок присваивания в a, b = b, a |
Если в условии звучит «числа от 1 до n» и «без дополнительной памяти», почти наверняка от вас ждут именно этот приём или его родственника — пометку знаком.
Интуиция: у каждого числа есть свой стул
Представьте стульев с номерами от 1 до и человек с билетами на эти же номера. Все сели как попало. Как рассадить их правильно, не выводя никого в коридор?
Подходим к первому стулу. На нём сидит человек с билетом №3. Пересаживаем его на стул №3, а того, кто сидел там, — на первый. Если и новый сосед не на своём месте, повторяем. Каждая пересадка ставит хотя бы одного человека на его законный стул, и больше его никто не трогает. Значит, пересадок будет не больше .
Почему «циклическая»? Любая перестановка раскладывается на циклы: 1 → 3 → 5 → 1 и так далее. Обмены на одной позиции прокручивают ровно один такой цикл, пока он не замкнётся.
Наивные решения и почему их мало
Задача: в массиве лежат различные числа от 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]
Обратите внимание на две детали.
- После обмена указатель
iне двигается. На позициюiпришло новое число, и его тоже надо проверить. - Условие —
nums[i] != nums[j], а неnums[i] != i + 1. Для массива без повторов это одно и то же, но как только появятся дубликаты, второй вариант зациклится. Об этом подробнее в разделе про ошибки.
Разбор на примере
Возьмём [3, 1, 5, 4, 2]:
| Шаг | i | Массив | Действие |
|---|---|---|---|
| 1 | 0 | [3, 1, 5, 4, 2] | 3 должно стоять на индексе 2 → обмен |
| 2 | 0 | [5, 1, 3, 4, 2] | 5 → индекс 4 → обмен |
| 3 | 0 | [2, 1, 3, 4, 5] | 2 → индекс 1 → обмен |
| 4 | 0 | [1, 2, 3, 4, 5] | 1 на месте → i += 1 |
| 5–8 | 1–4 | [1, 2, 3, 4, 5] | все на месте, указатель доходит до конца |
Три обмена на позиции 0 прокрутили цикл 1 → 3 → 5 → 2 → 1. Число 4 с самого начала было в цикле длины 1 и не двигалось.
Почему это , хотя внутри while есть «скрытый цикл»
Частый вопрос на собеседовании: «У вас указатель может стоять на месте много итераций подряд. Это точно не ?»
Аргумент такой. Каждая итерация цикла делает одно из двух:
- обмен — после него число
nums[j]стоит на своём месте и больше никогда не сдвинется, потому что мы трогаем только позиции, где число чужое. Таких событий не больше ; - сдвиг
i += 1— их ровно .
Итого не больше итераций. Это амортизированная оценка: тот же приём, что в монотонном стеке, где элемент кладут и вынимают не больше одного раза. Подробнее про такие рассуждения — в статье про O-нотацию.
Шаблон: расставь, потом найди нарушение
Почти все задачи паттерна решаются в две фазы:
- Расставить числа по местам, пропуская те, у которых нет места (ноль, отрицательные, больше ) или место уже занято таким же числом.
- Пройтись по массиву: позиция
i, гдеnums[i] != i + 1, — это и есть аномалия. Индекс говорит, какого числа не хватает (i + 1), а значение — какое число лишнее (nums[i]).
Дальше меняется только то, что именно мы возвращаем.
Missing Number: одно пропущенное из 0..n
LeetCode 268. Даны различных чисел из диапазона , одного не хватает. Здесь число v хочет стоять на индексе v, а для числа места нет — его пропускаем.
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. Массив длины , числа от 1 до , некоторые встречаются дважды, некоторые — ни разу. Верните все пропущенные.
Сумма тут не поможет: пропущенных может быть несколько. А шаблон работает без изменений: дубликат просто останется на чужом месте, когда его «родной» стул уже занят таким же числом.
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 до , но одно из них заменили копией другого. Верните [дубликат, пропущенное].
Здесь видно, зачем шаблон держит обе половины информации. На «сломанной» позиции значение — дубликат, а индекс + 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. Массив длины , числа от 1 до , ровно одно число повторяется (возможно, много раз). Найдите его.
Циклическая сортировка даёт ответ даже раньше конца: как только хотим поставить число на место, а там уже такое же, — это дубликат.
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. Дан произвольный массив целых чисел — с нулями, отрицательными, огромными значениями и повторами. Найдите наименьшее положительное число, которого в нём нет. Ограничения: по времени и дополнительной памяти.
Ключевое наблюдение
Ответ всегда лежит в диапазоне . Почему: в массиве ячеек, поэтому числа в лучшем случае все присутствуют, и тогда ответ . Если хотя бы одного не хватает, ответ меньше.
Отсюда вывод: всё, что или , на ответ не влияет. Такие числа можно просто оставить где лежат. Всё остальное — расставить циклической сортировкой.
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 | Массив | Действие |
|---|---|---|---|
| 1 | 0 | [3, 4, -1, 1] | 3 → индекс 2, обмен |
| 2 | 0 | [-1, 4, 3, 1] | −1 вне диапазона, i += 1 |
| 3 | 1 | [-1, 4, 3, 1] | 4 → индекс 3, обмен |
| 4 | 1 | [-1, 1, 3, 4] | 1 → индекс 0, обмен |
| 5 | 1 | [1, -1, 3, 4] | −1 вне диапазона, i += 1 |
| 6–7 | 2–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
Альтернатива: пометка знаком
Тот же эффект «массив как таблица флагов» можно получить без обменов. Сначала заменяем всё, что вне , на . Затем для каждого значения 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. Забыли про числа вне диапазона
Ноль, отрицательные и числа больше надо явно пропускать. В Python отрицательный индекс не упадёт, а тихо выдаст неверный ответ — это хуже исключения.
5. Смещение на единицу
Для диапазона число v стоит на индексе v - 1, для — на индексе v. Перед кодом проговорите, какой у вас диапазон, и проверьте граничные случаи: пустой массив, один элемент, пропущено самое большое число.
6. Испорченный вход без предупреждения
Все решения на месте меняют массив. В продакшен-коде это сюрприз для вызывающей стороны. На собеседовании это допустимо, но спросите разрешения или предложите сделать копию — тогда честная память будет .
Когда паттерн не подходит
- Значения не ограничены длиной массива. Если числа произвольные, «родного» индекса нет. Нужна хеш-таблица или сортировка.
- Вход менять нельзя. Тогда смотрите на сумму, XOR, Флойда или бинарный поиск по ответу (для задачи 287 он даёт без модификации; см. бинарный поиск по ответу).
- Нужен стабильный порядок или исходные позиции. Циклическая сортировка их уничтожает.
Где встречается на собеседованиях
Паттерн входит в набор, который кочует по популярным курсам подготовки к алгоритмическим секциям вместе с двумя указателями и скользящим окном. Чаще всего его проверяют так:
- First Missing Positive — любимая Hard-задача из-за жёсткого ограничения по памяти. Интервьюер ждёт наблюдения «ответ в » — это половина решения.
- Find the Duplicate Number — проверка, знаете ли вы и обмены, и Флойда, и умеете ли уточнить, можно ли менять вход.
- Find All Duplicates / Disappeared Numbers — на разминке или как follow-up после варианта с множеством: «а теперь без дополнительной памяти».
- Missing Number — простой вход в тему, где хорошо показать три решения (сумма, XOR, обмены) и сравнить их.
Как узнать задачу в незнакомой формулировке: ищите в условии «числа от 1 до n», «длина массива n», «найти пропущенное или лишнее» и « памяти». Если всё это есть, первым делом спросите себя: можно ли поставить каждое число на индекс, равный ему самому?
Итог
- Число
vиз диапазона имеет естественное место — индексv - 1. Массив можно использовать как свою же таблицу флагов. - Две фазы: расставить обменами, затем найти позиции, где
nums[i] != i + 1. - Время : каждый обмен навсегда ставит одно число на место. Память .
- Сравнивайте с целевой ячейкой (
nums[i] != nums[j]), вычисляйтеjзаранее и пропускайте числа вне диапазона. - Если вход трогать нельзя — переходите на сумму, XOR или алгоритм Флойда.