Объединение двух отсортированных массивов

Даны два отсортированных по возрастанию массива целых чисел nums1 и nums2, нужно объединить их в один отсортированный массив. Реализуйте функцию, которая принимает два массива и возвращает один объединенный отсортированный массив.

Примеры:

  1. Вход: nums1 = [1, 3, 5], nums2 = [2, 4, 6] Выход: [1, 2, 3, 4, 5, 6]
  2. Вход: nums1 = [0, 1, 2], nums2 = [1, 3, 5] Выход: [0, 1, 1, 2, 3, 5]
  3. Вход: nums1 = [1, 2, 3], nums2 = [] Выход: [1, 2, 3]

Мое решение

Я всегда начинаю решение с написания юнит тестов, хотя это не всегда хорошо и вот почему. Запуская тесты вы полагаетесь на ресурсы машины в вычислении каждой итерации. Куда более полезно вычислять каждую итерацию самостоятельно - во-первых, вы можете прокачать свою оперативную память запоминанием переменных в каждой итерации =) Ну и во-вторых, с ручкой проходя каждую строчку кода итерационно можно сделать удивительные открытия в своем коде.

@Test  
fun makeTest() {  
    Assert.assertTrue(intArrayOf(1, 2, 3, 4, 5, 6) sameAs mergeSortedArrays(intArrayOf(1, 3, 5), intArrayOf(2, 4, 6)))  
    Assert.assertTrue(intArrayOf(0, 1, 1, 2, 3, 5) sameAs mergeSortedArrays(intArrayOf(0, 1, 2), intArrayOf(1, 3, 5)))  
    Assert.assertTrue(intArrayOf(1, 3, 5) sameAs mergeSortedArrays(intArrayOf(1, 3, 5), intArrayOf()))  
    Assert.assertTrue(intArrayOf(0, 1, 2, 3, 6, 8, 9, 10) sameAs mergeSortedArrays(intArrayOf(0, 1, 6), intArrayOf(2, 3, 8, 9, 10)).also { println("===> ${it.toSet()}") })  
}

Вспомогательная функция для сравнения двух IntArray:

private infix fun IntArray.sameAs(other: IntArray): Boolean {  
    if (size != other.size) return false  
    for (i in indices) {  
        if (this[i] != other[i]) return false  
    }  
  
    return true  
}

Я решил использовать два указателя для прохода по двум массивам одновременно, сравнивая между собой текущие значения и увеличивая счетчик с наименьшим в паре значением. Звучит вполне логично.

fun mergeSortedArrays(nums1: IntArray, nums2: IntArray): IntArray {  
    val result = mutableListOf<Int>()  
    var index1 = 0  
    var index2 = 0  
  
    while (index1 < nums1.size || index2 < nums2.size) {  
        val num1 = nums1.getOrNull(index1)  
        val num2 = nums2.getOrNull(index2)  
  
        when {  
            num1 != null && num2 != null && num1 == num2 -> {  
                result.add(num1)  
                result.add(num2)  
  
                index1++  
                index2++  
            }  
  
            num1 != null && num2 != null -> {  
                if (num1 < num2) {  
                    index1++  
                    result.add(num1)  
                } else {  
                    index2++  
                    result.add(num2)  
                }  
            }  
  
            num2 != null -> {  
                result.add(num2)  
                index2++  
            }  
  
            num1 != null -> {  
                result.add(num1)  
                index1++  
            }  
        }  
    }  
  
    return result.toIntArray()  
}

Мое решение было одобрено как верное, но параллельно предложили еще один вариант, выбирайте сами какой вам больше понравился. Смысл плюс-минус похож.

fun mergeSortedArrays(nums1: IntArray, nums2: IntArray): IntArray {
    val merged = IntArray(nums1.size + nums2.size)
    var i = 0
    var j = 0
    var k = 0

    while (i < nums1.size && j < nums2.size) {
        if (nums1[i] <= nums2[j]) {
            merged[k] = nums1[i]
            i++
        } else {
            merged[k] = nums2[j]
            j++
        }
        k++
    }

    while (i < nums1.size) {
        merged[k] = nums1[i]
        i++
        k++
    }

    while (j < nums2.size) {
        merged[k] = nums2[j]
        j++
        k++
    }

    return merged
}

Объяснение:

  1. Два указателя:

    • Один указатель (i) проходит по первому массиву, а другой (j) по второму. Сравниваются текущие элементы двух массивов, и меньший из них добавляется в результирующий массив (merged).

  2. Оставшиеся элементы:

    • После завершения основного цикла могут остаться элементы в одном из массивов, которые еще не были добавлены в merged. Эти элементы добавляются оставшимися циклами.

  3. Возврат результата:

    • Возвращается полностью отсортированный объединенный массив.