1. Условие задачи
Дано: два отсортированных в неубывающем порядке массива nums1 и nums2, а также числа m и n — сколько «настоящих» элементов в каждом из них.
Нужно: слить их в один отсортированный массив. И вот здесь главный подвох задачи: результат надо записать прямо в nums1, ничего не возвращая. Для этого nums1 заранее сделали длины m + n — первые m позиций содержат его элементы, а последние n позиций забиты нулями-заглушками и должны быть перезаписаны. Массив nums2 имеет ровно длину n.
Ограничения: 0 <= m, n <= 200, 1 <= m + n <= 200, значения от -10^9 до 10^9. Один из массивов может быть пустым (тогда m = 0 или n = 0), но одновременно оба пустыми не бывают.
Пример: nums1 = [1, 2, 3, 0, 0, 0], m = 3, nums2 = [2, 5, 6], n = 3 → nums1 должен стать [1, 2, 2, 3, 5, 6].
Follow-up от LeetCode: решить за O(m + n) времени. Интервьюеру интересен не сам факт слияния, а красивый in-place приём.
2. Решение
Ключевое наблюдение: оба массива уже отсортированы. Значит, задача — это классический merge step из merge sort (если не знаешь что это – ничего страшного): если идти по обоим массивам одновременно, на каждом шаге в ответ надо забирать меньший из двух текущих кандидатов. Единственная сложность — как аккуратно писать результат прямо в nums1, не затирая ещё непрочитанные элементы.
Самое простое решение — дописать nums2 в свободный хвост nums1, а затем отсортировать весь массив. Оно работает за O((m + n) log(m + n)), но совсем не использует то, что оба исходных массива уже отсортированы. Поэтому код этого варианта разбирать не будем и сразу попробуем получить линейное время.
Первое решение: классическое слияние двух массивов
Воспользуемся той же логикой, что и на этапе слияния в merge sort. Ставим указатель p1 на начало полезной части nums1, а указатель p2 — на начало nums2. Сравниваем элементы под указателями и добавляем меньший в отдельный массив ans.
После добавления двигаем указатель того массива, откуда взяли элемент. Когда один массив закончился, дописываем в ans оставшийся хвост другого массива. В конце перезаписываем содержимое nums1 готовым ответом.
Алгоритм по шагам
- Создаём пустой массив
ans. - Ставим
p1 = 0иp2 = 0. - Пока в обоих массивах остались элементы, сравниваем
nums1[p1]иnums2[p2]. - Добавляем меньший элемент в
ansи сдвигаем соответствующий указатель. - Дописываем оставшиеся элементы полезной части
nums1, если они есть. - Дописываем оставшиеся элементы
nums2, если они есть. - Перезаписываем
nums1срезомnums1[:] = ans.
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
p1 = p2 = 0
ans = []
# 1. Пока в обоих массивах есть элементы — берём меньший
while p1 < m and p2 < n:
if nums1[p1] <= nums2[p2]:
ans.append(nums1[p1])
p1 += 1
else:
ans.append(nums2[p2])
p2 += 1
# 2. Дописываем хвост массива, который ещё не закончился
while p1 < m:
ans.append(nums1[p1])
p1 += 1
while p2 < n:
ans.append(nums2[p2])
p2 += 1
# 3. Перезаписываем исходный список, не создавая нового nums1
nums1[:] = ans
Важно использовать именно nums1[:] = ans, а не nums1 = ans. Во втором случае локальная переменная nums1 просто начнёт ссылаться на другой список, но переданный в функцию исходный список не изменится. Присваивание срезу заменяет содержимое того же объекта, как и требует условие.
Это уже классическое линейное слияние за O(m + n). Но массив ans хранит все m + n элементов, поэтому дополнительная память тоже равна O(m + n). Можно ли избавиться от него и писать ответ сразу в nums1? Да — если поменять направление обхода.
Идея оптимального решения: два указателя, но пишем с конца
Главный инсайт: в конце nums1 есть свободное место — те самые n нулей-заглушек. Значит, если писать результат туда, задом наперёд, мы гарантированно не затираем непрочитанные данные.
Ставим три указателя:
p1 = m - 1— последний реальный элемент вnums1;p2 = n - 1— последний элемент вnums2;p = m + n - 1— куда пишем (в самый хвост).
На каждом шаге сравниваем nums1[p1] и nums2[p2], кладём больший в nums1[p] и сдвигаем соответствующий указатель влево. p сдвигаем всегда.
Почему запись никогда не догонит чтение — интуитивно: между p1 и p изначально ровно n свободных ячеек. На каждой итерации либо p1 и p сдвигаются вместе (тогда разрыв не меняется), либо сдвигается только p2 и p — тогда разрыв сокращается на 1. Уменьшить p2 можно максимум n раз, значит разрыв никогда не станет отрицательным. То есть p физически не может обогнать p1.
Тонкий момент про выход из цикла. Достаточно гонять цикл, пока p2 >= 0. Если nums2 кончился раньше — оставшиеся элементы nums1 уже лежат ровно там, где должны, трогать их не нужно. А вот если nums1 кончился раньше (p1 < 0), а в nums2 ещё что-то осталось — надо докладывать хвост nums2. Это удобно спрятать в одну ветку else.
Алгоритм по шагам
- Ставим
p1 = m - 1,p2 = n - 1,p = m + n - 1. - Пока
p2 >= 0: - Если
p1 >= 0иnums1[p1] > nums2[p2]— пишемnums1[p1]вnums1[p], сдвигаемp1 -= 1. - Иначе — пишем
nums2[p2]вnums1[p], сдвигаемp2 -= 1. - Сдвигаем
p -= 1в любом случае. - Когда
p2 < 0, останавливаемся: всё, что осталось отnums1, уже на своих местах.
Визуализация на nums1 = [1, 2, 3, 0, 0, 0], m = 3, nums2 = [2, 5, 6], n = 3
Старт: p1 = 2 (значение 3), p2 = 2 (значение 6), p = 5.
| Шаг | p1 | p2 | p | nums1[p1] | nums2[p2] | Кто больше | Пишем в nums1[p] | Состояние nums1 |
|---|---|---|---|---|---|---|---|---|
| 1 | 2 | 2 | 5 | 3 | 6 | nums2 | 6 → nums1[5], p2 = 1 | [1, 2, 3, 0, 0, 6] |
| 2 | 2 | 1 | 4 | 3 | 5 | nums2 | 5 → nums1[4], p2 = 0 | [1, 2, 3, 0, 5, 6] |
| 3 | 2 | 0 | 3 | 3 | 2 | nums1 | 3 → nums1[3], p1 = 1 | [1, 2, 3, 3, 5, 6] |
| 4 | 1 | 0 | 2 | 2 | 2 | ничья → nums2 | 2 → nums1[2], p2 = −1 | [1, 2, 2, 3, 5, 6] |
| 5 | — | — | — | — | — | p2 < 0, стоп | — | [1, 2, 2, 3, 5, 6] |
Шаг 4 — красивый: при ничьей пишем из nums2 (ветка else), после чего p2 уходит в -1, цикл завершается. Первые два элемента nums1 (1 и 2) не трогали — они и должны стоять на этих местах.
Код на Python
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
# 1. Три указателя: два чтения (с конца обоих массивов) и один записи
p1, p2, p = m - 1, n - 1, m + n - 1
# 2. Идём, пока в nums2 есть непереложенные элементы
while p2 >= 0:
# 3. Берём больший из двух кандидатов и пишем в хвост nums1
if p1 >= 0 and nums1[p1] > nums2[p2]:
nums1[p] = nums1[p1]
p1 -= 1
else:
nums1[p] = nums2[p2]
p2 -= 1
p -= 1
# 4. Если p1 остался — эти элементы уже на своих местах, ничего не делаем
Краевые случаи
n == 0— цикл ни разу не запустится,nums1уже в нужном виде.m == 0—p1 = -1, условиеp1 >= 0всегда ложно, поэтому каждый раз пишем изnums2. По сути просто копируемnums2вnums1.- Все элементы
nums1меньше всех элементовnums2— цикл сначала перепишет весьnums2в хвостnums1,p1так и останется наm - 1(то есть в началеnums1), там всё уже отсортировано. - Все элементы
nums1больше всех элементовnums2— цикл сначала перекинет весьnums1в хвост, потом добьётnums2в начало. - Дубликаты и равные элементы — ветка
elseберёт изnums2, порядок стабильный, ответ корректный. - Отрицательные числа — сравнение целых работает без сюрпризов.
3. Сложность алгоритма
- Каждая итерация цикла двигает как минимум один указатель влево. Всего указатели могут сдвинуться
m + nраз, а значит итераций не большеm + n. - Внутри итерации — только сравнение и присваивание.
- Дополнительной памяти не используем: работаем прямо в
nums1.
Итог по времени: O(m + n).
Итог по памяти: O(1) дополнительной.
Пояснения: почему обязательно писать с конца
В первом решении мы шли двумя указателями с начала, как в классическом merge из merge sort, и складывали результат в отдельный ans. Если попробовать тем же способом писать сразу в nums1[0], nums1[1], …, мы начнём затирать ещё непрочитанные значения nums1.
Разворот направления решает проблему без копий. Свободные ячейки (нули-заглушки) уже в хвосте — так и пишем туда, задом наперёд. Приём универсальный: если нужно модифицировать массив in-place, и свободное место есть с одного края — итерируй с этого края. В комментариях к топовому решению niits этот же приём разобран пошагово; он же — Approach 3 из официального Editorial с пометкой «medium-level solution for an easy problem».
Пояснения: почему цикл только по p2 >= 0
В Approach 3 из Editorial цикл идёт ровно m + n раз с break при p2 < 0. Логически то же самое, но в топ-решениях сообщества (Amirali Sharifzad, niits) любят условие while p2 >= 0 — оно короче и подчёркивает главную инвариант: как только nums2 закончился — задача решена.
Всё, что осталось в nums1 слева от p1, уже отсортировано (это исходный nums1) и уже стоит на своих финальных позициях (мы туда ни разу не писали, потому что разрыв между p и p1 начинается на n и не уходит в минус). Ничего доперекладывать не нужно.
А вот обратная ситуация — когда nums1 кончился раньше (p1 = -1) — обязательно требует продолжения цикла: там ещё остались элементы nums2, которые нужно вручную докинуть в начало. За это отвечает проверка p1 >= 0 внутри if — если она провалилась, автоматически идём в ветку else и пишем из nums2, пока он не кончится.
Вывод
Паттерн задачи: если модифицируешь массив in-place, а свободное место лежит с одного края — итерируй с этого края. Так исчезает необходимость в отдельном массиве ответа, и merge из O(m + n) времени + O(m + n) памяти превращается в O(m + n) времени + O(1) памяти — ровно то, что просит follow-up.
Второй урок — про честность на собеседовании. Одного решения с nums1.sort() обычно недостаточно: интервьюер хочет увидеть, что ты умеешь пользоваться тем, что массивы уже отсортированы, а обход с конца — небольшой, но узнаваемый трюк, который отличает «прошёл LeetCode» от «понимает, что делает».
🐆