Merge Sorted Array

Лёгкая№88два массива

Даны два массива, отсортированных по возрастанию. В конце первого — пустые ячейки, ровно столько, сколько чисел во втором. Нужно влить второй массив в первый, прямо в нём, чтобы первый остался отсортированным. Наш пример: [2, 5, 8, _, _, _] и [1, 6, 9] дают [1, 2, 5, 6, 8, 9].

88 Merge Sorted ArrayРазбор · 1×

Пример: nums1 = [2, 5, 8, _, _, _] и nums2 = [1, 6, 9]. Три указателя идут справа налево: i по числам nums1, j по nums2, write по ячейкам, которые заполняем.

nums2nums1011629021528345i
ещё не поставленысравниваем или переносимтолько что записанона своём местеуже перенесенопусто

i — на последнем числе nums1, 8

01/38
сначала · назад · пуск · шаг
Скорость
1function merge(nums1, m, nums2, n):
2 i = m - 1
3 j = n - 1
4 write = m + n - 1
5 while j >= 0:
6 if i >= 0 and nums1[i] > nums2[j]:
7 nums1[write] = nums1[i]
8 i = i - 1
9 else:
10 nums1[write] = nums2[j]
11 j = j - 1
12 write = write - 1
13 return nums1
состояние
i
2
j
–
write
–
nums1
[2, 5, 8, _, _, _]
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Самое большое из всех чисел — большее из двух последних, и его место — последняя ячейка. Дальше то же самое с остальными, поэтому результат заполняем с конца, каждый раз самым большим из оставшихся.
  2. С конца мы не затираем ни одного числа, которое ещё нужно: write всегда правее i, поэтому попадает либо на пустую ячейку, либо на число, которое уже переехало.
  3. Когда nums2 закончился, оставшиеся числа nums1 уже стоят на своих местах, и цикл на этом останавливается.

Сложность

Время O(m + n): каждый шаг ставит на место одно число. Память O(1): сливаем прямо в nums1, без третьего массива.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.