Слияние отсортированных массивов – DEV Community 👩‍💻👨‍💻

Давайте разберем задачу слияния двух отсортированных массивов. Ее можно найти вот здесь Merge Sorted Array

Постановка задачи

Дано два массива nums1 и nums2, отсортированных в неубывающем порядке, и два числа m и n, озночающих количество элементов в соответствующих массивах.
Необходимо объединить два массива в один, отсортированный в неубывающем порядке.
Итоговый массив должен должен возвращен в переменной nums1.

Пример входных данных

Пример 1

Входные даные:
nums1 = [1, 2, 3, 0, 0, 0]
m = 3
nums2 = [2, 5, 6]
n = 3
Результат:
[1, 2, 2, 3, 5, 6]

Пример 2

Входные даные:
nums1 = [1]
m = 1
nums2 = []
n = 0
Результат:
[1]

Пример 3

Входные даные:
nums1 = [0]
m = 0
nums2 = [1]
n = 1
Результат:
[1]

Решение

Нам необходимо итерироваться по обоим массивам от начала до конца. На каждой итерации мы берем минимальный элемент и кладем его в новый массив. Далее необходимо скопировать этот массив в nums1.
Однако в таком случаем мы будем использовать дополнительное пространство. Это можно оптимизировать. По условию в массиве nums1 выделено место m + n. Таким образом, если мы начнем заполнять массивы с конца, то сможем обойтись без дополнительного пространства.

Решение по шагам

1) Сначала нам необходимо инициализировать счетчики.

var index1: Int = m - 1
var index2: Int = n - 1
var index: Int = m + n - 1

Для первого и второго массива мы будем использовать index1 и index2. Для отслеживания результирующего индекса будем использовать index.

2) Затем нам надо определить условия цикла.

while (index >= 0 && index2 >= 0) {
   ...
}

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

3) Теперь нам необходимо реализовать условия выбора элемента и обновления индекса

if (index1 >= 0 && nums1[index1] > nums2[index2]) {
    nums1[index] = nums1[index1]
    index1--
} else {
    nums1[index] = nums2[index2]
    index2--
}
index--

Проверяем, что не достигли начала первого списка, и очередной элемент в первом списке больше очередного элемента во втором. Тогда берем из первого списка и уменьшаем счетчик на первом. Иначе берем из второго списка и уменьшаем на втором. Общий счетчик уменьшаем на каждой итерации.

Оценка сложности

• По времени – O(nums1.length + nums2.length). Мы полностью проходимся по обоим массивам.
• По памяти – O(1). Мы используем только индексы. Объем используемой памяти не зависит от размеров входных массивов.

Полное решение

fun merge(nums1: IntArray, m: Int, nums2: IntArray, n: Int) {
    var index1: Int = m - 1
    var index2: Int = n - 1
    var index: Int = m + n - 1
    while (index >= 0 && index2 >= 0) {
        if (index1 >= 0 && nums1[index1] > nums2[index2]) {
            nums1[index] = nums1[index1]
            index1--
        } else {
            nums1[index] = nums2[index2]
            index2--
        }
        index--
    }
}