🗂

100日アルゴリズム[12日目・ソート]

2024/04/09に公開

問題

https://leetcode.com/problems/merge-sorted-array/description/

回答

/**
 Do not return anything, modify nums1 in-place instead.
 */
function merge(nums1: number[], m: number, nums2: number[], n: number): void {
    let i = m-1
    let j = n-1
    let k = m+n-1

    while(i >= 0 && j >= 0) {
        if(nums1[i] > nums2[j]) {
            nums1[k--] = nums1[i--]
        } else {
            nums1[k--] = nums2[j--]
        }
    }

    while(j >=0 ) {
        nums1[k--] = nums2[j--]
    }
};

nums1内の配列に、nums1.lengthのn個分の要素とnums2.lengthのm個分の要素、計n+m-1個分の要素をソートした状態で保存する必要があったので、それぞれの配列の末尾の値を評価して、大きい方をnums1の一番後ろに追加するようにしました。

最後に、まだnums2の中に未評価の値がある場合を考え、それらの値はnums1の先頭に加えるようにしました。

Discussion