DEV Community 👩‍💻👨‍💻

Ivan
Ivan

Posted on

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

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

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

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

while (index >= 0 && index2 >= 0) {
   ...
}
Enter fullscreen mode Exit fullscreen mode

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

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

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

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

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

  • По времени - 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--
    }
}
Enter fullscreen mode Exit fullscreen mode

Top comments (2)

Collapse
 
irchiiik profile image
Ирина Лютина

🧐👍

Collapse
 
newnew53121785 profile image
marah ahmad

Nice really

Join us at DEV
Yes, this is technically an “ad”, but really we just want to ask if you want to join DEV. We have 900k+ developers reading, posting, and enjoying community, and would love to have you.   Create an account and continue your coding journey.