0088. Merge Sorted Array - chasel2361/leetcode GitHub Wiki

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
Note:
The number of elements initialized in nums1 and nums2 are m and n respectively.
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.

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

題目要求在 in-place 的條件下將給定的兩個已排序陣列合併，由於 nums1 有提供空位，因此題目還給了兩個陣列排除空格後的長度 m, n。

這題可以利用 m, n 來進行合併，由於 nums1 的空位給在尾端，所以較好的方式為從尾部開始針對陣列數值比較大小，寫作程式碼如下

[1] 將 m, n 視為一個指標，當值為零表示指標走到盡頭。由於本題要求將 nums2 併入 nums1，因此當 n 值為零時表示排序完成。
[2] 第一個條件是 nums1 走完，但 nums2 尚未完全併入 nums1。第二個條件為 m 指標值小於 n 指標值，此時將 n 指標值放入 m+n-1 位置(nums2 值併入 nums1)
[3] 反之將 nums1 值往後挪

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        while n > 0:  # [1]
            if m <= 0 or nums1[m-1] < nums2[n-1]:  # [2]
                nums1[m+n-1] = nums2[n-1]
                n -= 1
            else:  # [3]
                nums1[m+n-1] = nums1[m-1]
                m -= 1

這樣寫的時間複雜度是 O(N)，空間複雜度為 O(1)

不過思考了一下之後，覺得可以訂出幾個變數來把程式碼寫得更清楚且快速

N1 = m-1   # nums1 指標位置
N2 = n-1   # nums2 指標位置
K = m+n-1  # 待儲存位置

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        N1, N2 = m-1, n-1
        K = m+n-1
        
        while N2 >= 0:
            if N1 < 0 or nums1[N1] < nums2[N2]:
                nums1[K] = nums2[N2]
                N2 -= 1
                K -= 1
            else:
                nums1[K] = nums1[N1]
                N1 -= 1
                K -= 1

這樣雖然沒有改變解題思路，但實際運行時可以減少很多無謂的計算量，並且讓程式碼好讀很多