Merge Sorted Array

Q: Какова временная сложность слияния двух отсортированных массивов?

С двумя указателями это O(m + n) , где m и n — длины двух массивов. На каждом шаге размещается одно значение, и ни одно значение не рассматривается дважды. Конкатенация и сортировка вместо этого требуют O((m + n) log(m + n)) .

Q: Как объединить два отсортированных массива на месте?

Если в конце первого массива есть место для обоих массивов, заполняй его с конца. Сравнивай наибольшие оставшиеся значения двух массивов, записывай большее из них в последнюю свободную ячейку и сдвигайся влево. Запись с конца никогда не перезаписывает ещё не размещённое значение первого массива, поэтому второй массив не нужен.

Q: Объединение двух отсортированных массивов — это то же самое, что этап слияния в сортировке слиянием?

Да. Сортировка слиянием делит массив на две половины, сортирует каждую из них, а затем объединяет две отсортированные половины именно этим циклом с двумя указателями. Выбор левого значения при равенстве сохраняет исходный порядок одинаковых значений, благодаря чему сортировка слиянием является устойчивой.

Q: Почему бы не объединить массивы и вызвать сортировку?

Он дает правильный ответ и на практике часто работает быстро. Но он не учитывает, что входные данные уже отсортированы, и добавляет множитель log . На собеседовании ожидается слияние с помощью двух указателей, потому что оно показывает, что ты умеешь использовать заданный порядок.

ЛегкоДва указателя Сортировка

+10

Тебе даны два массива целых чисел, nums1 и nums2. Каждый из них уже отсортирован в неубывающем порядке. Верни один массив, содержащий все значения из обоих массивов, также в неубывающем порядке. Значение, которое встречается в обоих массивах, должно встречаться в результате столько раз, сколько оно встречается в общей сложности.

Функция

merge(nums1: integer-array, nums2: integer-array) → integer-array

nums1integer-array: первый отсортированный массив
nums2integer-array: второй отсортированный массив
Возвращаетinteger-array: все значения обоих массивов в одном отсортированном массиве длиной nums1.length + nums2.length

Ограничения

1 ≤ nums1.length, nums2.length ≤ 2000
-10⁵ ≤ nums1[i], nums2[j] ≤ 10⁵
nums1 и nums2 отсортированы каждый в неубывающем порядке.

Примеры

Ввод: nums1 = [1, 4, 9]nums2 = [2, 3, 10]
Вывод: [1, 2, 3, 4, 9, 10]
Пояснение: Сравнивайте два первых элемента и оставляйте меньший: 1, затем 2 и 3 из nums2, затем 4 и 9 из nums1, а в конце — 10. В результате содержатся все шесть значений.

Ввод: nums1 = [-5, 0, 0, 8]nums2 = [0, 6]
Вывод: [-5, 0, 0, 0, 6, 8]
Пояснение: 0 встречается дважды в nums1 и один раз в nums2, поэтому в результате три 0. -5 меньше всех элементов в nums2 и идет первым.

+13 скрытых тестов при отправке

Дополнительный вопрос

Можешь ли ты объединить k отсортированных массивов, содержащих в общей сложности N значений, за время O(N log k)?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Объединение массивов и сортировка дают правильный ответ, но при этом теряется тот факт, что обе половины уже отсортированы. Наименьшее из оставшихся значений всегда находится в начале одного из двух массивов. Заведите по одному индексу для каждого массива, на каждом шаге берите меньшее из первых значений — и за один проход получите результат. Это шаг слияния в сортировке слиянием.

Объедините и отсортируйте

Идея

Поместите каждое значение из nums1 и каждое значение из nums2 в один массив, а затем отсортируйте его. В результате будут нужные значения, каждое столько раз, сколько оно встречалось, в нужном порядке.

Для [1, 4, 9] и [2, 3, 10] объединённый массив — [1, 4, 9, 2, 3, 10], а после сортировки получается [1, 2, 3, 4, 9, 10].

Если в nums1 содержится m значений, а в nums2 — n, обычная сортировка требует O((m + n) log(m + n)). Она работает и достаточно быстрая при этих ограничениях, но не использует уже заданный отсортированный порядок. Следующий подход использует его и устраняет множитель log.

Алгоритм

Создай массив со значениями nums1, за которыми следуют значения nums2.
Отсортируй его по возрастанию числового значения.
Верни его.

def merge(nums1, nums2):
    return sorted(nums1 + nums2)

Два указателя, по одному на каждый массив

Идея

Храни индексы i в nums1 и j в nums2, оба начинаются с 0. Всё, что находится до i и до j, уже добавлено в результат. Наименьшее ещё не использованное значение — это nums1[i] или nums2[j], поскольку каждый массив отсортирован и его оставшиеся значения могут быть только больше. Добавь меньшее значение и сдвинь соответствующий индекс.

Для массивов [1, 4, 9] и [2, 3, 10]: 1 меньше 2, затем 2 меньше 4, 3 меньше 4, 4 меньше 10, 9 меньше 10. Теперь значения в nums1 закончились, поэтому оставшаяся часть nums2, то есть [10], копируется как есть. Результат — [1, 2, 3, 4, 9, 10].

На каждом шаге записывается одно значение, поэтому цикл выполняется m + n раз: время — O(m + n). Массив результата — единственная дополнительная память.

Алгоритм

Установи i и j равными 0 и создай пустой результат.
Пока в обоих массивах остаются элементы, сравнивай nums1[i] и nums2[j].
Добавь меньший элемент и передвинь его индекс вперёд. При равенстве выбери nums1[i].
Когда в одном из массивов закончатся элементы, добавь всё, что осталось в другом.
Верни результат.

def merge(nums1, nums2):
    result = []
    i = j = 0
    while i < len(nums1) and j < len(nums2):
        if nums1[i] <= nums2[j]:
            result.append(nums1[i])
            i += 1
        else:
            result.append(nums2[j])
            j += 1
    # one array is used up; the rest of the other is already sorted
    result.extend(nums1[i:])
    result.extend(nums2[j:])
    return result

Ловушки и крайние случаи

Большинство ошибок возникает в тот момент, когда один массив заканчивается, или из-за способа сравнения значений.

Остановить цикл, как только один массив закончится, и забыть про оставшиеся элементы другого. Для [1, 2, 3] и [4, 5, 6] цикл завершается после 1, 2 и 3, а 4, 5, 6 всё ещё нужно скопировать.
Обращаться к nums1[i] после того, как i достиг конца массива. Перед сравнением проверь оба индекса.
Терять дубликаты. [0, 0] и [0] сливаются в [0, 0, 0], а не в [0].
В JavaScript и TypeScript вызов sort() без компаратора сортирует числа как текст, поэтому [-5, 10, 9] сортируется в [-5, 10, 9]. Передай (a, b) => a - b.
В Lua и R массивы начинаются с 1, поэтому оба индекса начинаются с 1, а для границ используется <=.

Частые вопросы4

Какова временная сложность слияния двух отсортированных массивов?

С двумя указателями это O(m + n), где m и n — длины двух массивов. На каждом шаге размещается одно значение, и ни одно значение не рассматривается дважды. Конкатенация и сортировка вместо этого требуют O((m + n) log(m + n)).

Как объединить два отсортированных массива на месте?

Если в конце первого массива есть место для обоих массивов, заполняй его с конца. Сравнивай наибольшие оставшиеся значения двух массивов, записывай большее из них в последнюю свободную ячейку и сдвигайся влево. Запись с конца никогда не перезаписывает ещё не размещённое значение первого массива, поэтому второй массив не нужен.

Объединение двух отсортированных массивов — это то же самое, что этап слияния в сортировке слиянием?

Да. Сортировка слиянием делит массив на две половины, сортирует каждую из них, а затем объединяет две отсортированные половины именно этим циклом с двумя указателями. Выбор левого значения при равенстве сохраняет исходный порядок одинаковых значений, благодаря чему сортировка слиянием является устойчивой.

Почему бы не объединить массивы и вызвать сортировку?

Он дает правильный ответ и на практике часто работает быстро. Но он не учитывает, что входные данные уже отсортированы, и добавляет множитель log. На собеседовании ожидается слияние с помощью двух указателей, потому что оно показывает, что ты умеешь использовать заданный порядок.

Python

def merge(nums1, nums2):
    # Напишите код здесь

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

nums1 = [1, 4, 9]
nums2 = [2, 3, 10]

Ожидается

[1, 2, 3, 4, 9, 10]