Слияние отсортированных массивов

#kotlin #algorithms #leetcode #easy

Давайте разберем задачу слияния двух отсортированных массивов. Ее можно найти вот здесь 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--
    }
}