若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。
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
沒有留言:
張貼留言