Merge Sorted Array

Условие

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

Примеры

Input: nums1 = [1, 2, 3, 0, 0, 0], m = 3, nums2 = [2, 5, 6], n = 3

Output: [1, 2, 2, 3, 5, 6]

Explanation: Объединенный отсортированный массив — [1, 2, 2, 3, 5, 6].

Input: nums1 = [1], m = 1, nums2 = [], n = 0

Output: [1]

Explanation: Массив nums2 пустой, поэтому nums1 остается без изменений.

Input: nums1 = [0], m = 0, nums2 = [1], n = 1

Output: [1]

Explanation: Массив nums1 изначально пуст, поэтому результатом будет nums2.

Решение

fun merge(nums1: IntArray, m: Int, nums2: IntArray, n: Int) {
    var i = m - 1 // Индекс последнего элемента в nums1
    var j = n - 1 // Индекс последнего элемента в nums2
    var k = m + n - 1 // Индекс последнего места в nums1 для слияния

    // Проходим с конца обоих массивов и вставляем наибольший элемент на текущее место в nums1
    while (i >= 0 && j >= 0) {
        if (nums1[i] > nums2[j]) {
            nums1[k--] = nums1[i--] // Если текущий элемент в nums1 больше, ставим его на место
        } else {
            nums1[k--] = nums2[j--] // Если текущий элемент в nums2 больше или равен, ставим его на место
        }
    }

    // Если в nums2 остались элементы, переносим их в nums1
    // (если i < 0, то nums1 уже полностью заполнен)
    while (j >= 0) {
        nums1[k--] = nums2[j--]
    }
}

Временная сложность

O(m + n) — требуется один проход по двум массивам.

Пространственная сложность

O(1) — дополнительная память не используется, все происходит на месте.