88. Merge Sorted Array

問題URL

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

解法1

nums1とnums2をガッチャンコしてソートする。

func merge(nums1 []int, m int, nums2 []int, n int) {
    nums1 = append(nums1[:m], nums2...)
    slices.Sort(nums1)
}

解法2

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order

問題文にある「nums1とnums2は昇順にソートされている」という条件を利用する。

nums1とnums2の末尾（大きい値）から順に、大小比較して並べていく。

func merge(nums1 []int, m int, nums2 []int, n int) {
    for n > 0 {
        if m == 0 || nums2[n-1] > nums1[m-1] {
            nums1[n+m-1] = nums2[n-1]
            n--
        } else {
            nums1[n+m-1] = nums1[m-1]
            m--
        }
    }
}

感想

計算量の少ない解法2を、パッと思いつけるようになりたい。