88. Merge Sorted Array — разбор задачи

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 sort (сортировке слиянием), классическом алгоритме сортировки. Если ты пока не знаешь, что это такое, это абсолютно окей: для понимания этой задачи знать merge sort не нужно. Саму логику слияния мы разберём здесь с нуля.

Начнём с самого прямолинейного решения: соберём все нужные элементы, отсортируем их и запишем результат в nums1. Затем постепенно избавимся от лишних копий и от самой сортировки.

Самое простое решение: срезы, склейка и сортировка

Берём первые m элементов nums1 и первые n элементов nums2. Склеиваем эти два среза, сортируем получившийся список и перезаписываем содержимое исходного nums1.

from typing import List


class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        # Берём только нужные элементы и склеиваем их
        ans = nums1[:m] + nums2[:n]
        # Сортируем собранный список
        ans.sort()
        # Перезаписываем содержимое исходного nums1
        nums1[:] = ans

Например, из nums1 = [1, 2, 3, 0, 0, 0] при m = 3 берём [1, 2, 3], а из nums2 = [2, 5, 6] при n = 3 берём [2, 5, 6]. После склейки получаем [1, 2, 3, 2, 5, 6], после сортировки получаем [1, 2, 2, 3, 5, 6] и записываем его в nums1.

То же самое можно записать одной строкой: nums1[:] = sorted(nums1[:m] + nums2[:n]). Здесь важно присваивание срезу nums1[:]: оно меняет исходный список, тогда как nums1 = ans только переключило бы локальную переменную на другой список.

Общая верхняя оценка времени с учётом сортировки: O((m + n) log(m + n)). Дополнительная память: O(m + n), потому что создаём срезы и отдельный массив ответа.

Решение в лоб (Brute Force)

Теперь уберём срезы и отдельный ans: в хвосте nums1 уже есть ровно n свободных ячеек. Впишем туда nums2, а затем отсортируем весь nums1.

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        # 1. Копируем nums2 на место нулей-заглушек в хвосте nums1
        for i in range(n):
            nums1[m + i] = nums2[i]
        # 2. Сортируем nums1 in-place
        nums1.sort()

Ответ получаем прямо в nums1, но по-прежнему поручаем всю работу сортировке. Общая верхняя оценка времени остаётся O((m + n) log(m + n)); дополнительная память может достигать O(m + n) внутри сортировки, хотя своего массива ans у нас больше нет.

А можно обойтись вообще без сортировки и самостоятельно слить два уже отсортированных массива за O(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) дополнительной.

Пояснения: почему обязательно писать с конца

В решении со слиянием в отдельный ans мы шли двумя указателями с начала, как в классическом merge из merge sort. Если попробовать тем же способом писать сразу в 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» от «понимает, что делает».

🐆

1. Условие задачи

2. Решение

Самое простое решение: срезы, склейка и сортировка

Решение в лоб (Brute Force)

Классическое слияние двух массивов

Алгоритм по шагам

Идея оптимального решения: два указателя, но пишем с конца

Алгоритм по шагам

Визуализация на nums1 = [1, 2, 3, 0, 0, 0], m = 3, nums2 = [2, 5, 6], n = 3

Код на Python

Краевые случаи

3. Сложность алгоритма

Пояснения: почему обязательно писать с конца

Пояснения: почему цикл только по p2 >= 0

Вывод

Визуализация на `nums1 = [1, 2, 3, 0, 0, 0]`, `m = 3`, `nums2 = [2, 5, 6]`, `n = 3`

Пояснения: почему цикл только по `p2 >= 0`