LeetCode 解題練習：Merge Sorted Array

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

If you like this post, please click the ads on the blog or buy me a coffee. Thank you very much.

題目原文描述 https://leetcode.com/problems/merge-sorted-array/ 

中文描述

給定兩個由小排到大的陣列 nums1, nums2，以及兩個整數m, n 分別來表示陣列 nums1 與 nums2 的元素有多少個。請將 nums1與 nums2 合併成新的由小排到大之陣列。請將此陣列存到 nums1 裡，因此 nums1 長度為 m + n，其中最後 n 個元素都是 0。

範例一：

輸入 nums1 = [1, 3, 5, 7, 0, 0, 0], m = 4, nums2 = [2, 4, 6], n = 3 

輸出 [1, 2, 3, 4, 5, 6, 7]

範例二：

輸入 nums1 = [1, 3, 5, 7], m = 4, nums2 = [], n = 0 

輸出 [1, 3, 5, 7]

範例三：

輸入 nums1 = [], m = 0, nums2 = [2, 4, 6], n = 3 

輸出 [2, 4, 6]

解法：

比較兩陣列最右邊的元素nums1[a] 與 nums2[b]，merged 的最右邊元素merged[w]設定為較大的那一個。請參考下圖動畫：

Python Code

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.

        """

        w, a, b = m + n - 1, m - 1, n - 1

        while b >= 0:

            if a >= 0 and nums1[a] > nums2[b]:

                nums1[w] = nums1[a]

                a -= 1

            else:

                nums1[w] = nums2[b]

                b -= 1

            w -= 1