Ինչպե՞ս կարելի է երկու դասավորված զանգվածները միացնել նոր դասավորված զանգվածի մեջ, օգտագործելով լրացուցիչ հիշողություն։

Երկու դասավորված զանգվածները միացնելու համար նոր դասավորված զանգվածի մեջ, օգտագործելով լրացուցիչ հիշողություն, կարելի է կիրառել միացման ալգորիթմ (merge), որը նման է միացման քայլին դասավորության ժամանակ:

Նկատում:

1. Ստեղծեք նոր զանգված, որի չափը հավասար է երկու սկզբնական զանգվածների չափերի գումարին:
2. Օգտագործեք երկու ցուցիչ, յուրաքանչյուրը՝ մեկ զանգվածի համար:
3. Համեմատեք երկու զանգվածների ընթացիկ տարրերը, փոքրին ավելացրեք նոր զանգվածին և շարժեք համապատասխան ցուցիչը:
4. Երբ մեկը զանգվածներից ավարտվի, ավելացրեք մյուսի մնացած տարրերը:

Օրինակ Kotlin (Android)-ում:

fun mergeSortedArrays(arr1: IntArray, arr2: IntArray): IntArray {
    val result = IntArray(arr1.size + arr2.size)
    var i = 0
    var j = 0
    var k = 0

    while (i < arr1.size && j < arr2.size) {
        if (arr1[i] <= arr2[j]) {
            result[k++] = arr1[i++]
        } else {
            result[k++] = arr2[j++]
        }
    }

    while (i < arr1.size) {
        result[k++] = arr1[i++]
    }

    while (j < arr2.size) {
        result[k++] = arr2[j++]
    }

    return result
}

Այս ալգորիթմը աշխատում է ժամանակում O(n + m), որտեղ n և m՝ զանգվածների չափերն են, և օգտագործում է լրացուցիչ հիշողություն նոր զանգվածի համար: