Слияние отсортированных массивов
Tags: kotlin, algorithms, leetcode, easy
Published: 2022-08-31 08:54:03

Давайте разберем задачу слияния двух отсортированных массивов. Ее можно найти вот здесь [Merge Sorted Array](https://leetcode.com/problems/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)** Сначала нам необходимо инициализировать счетчики.

```kotlin
var index1: Int = m - 1
var index2: Int = n - 1
var index: Int = m + n - 1
```
Для первого и второго массива мы будем использовать переменные index1 и index2, соответственно. Для отслеживания результирующего индекса будет использоваться переменная index.

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

```kotlin
while (index >= 0 && index2 >= 0) {
   ...
}
```
Проверяется два условия. Если индекс результирующего массива равен нулю, значит мы уже заполнили весь массив, и необходимо останавливать итерации. Если индекс второго массива равен нулю, значит мы полностью проитерировались по второму массиву. Остаток первого массива расположен в правильном порядке, и мы можем спокойно заканчивать наш цикл.

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

```kotlin
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). Объем используемой памяти не зависит от размеров входных массивов, поскольку для решения задачи используются только индексы.

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

```kotlin
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--
    }
}
```