從LeetCode學演算法

0088. Merge Sorted Array (Easy)

Question

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:

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

1
Output: [1,2,2,3,5,6]

分析/解題

這題雖然相對比較無聊，
但merge的過程中其實蠻像merge sort的merge的，
所以選來讓讀者熟悉一下merge的概念，對上上篇提的應該會有幫助。

題目給定兩個陣列及有放元素的對應長度，兩者除了未放元素的0以外，
其他均已排序。同時，題目也假設第一個陣列必定有足夠空間，
可以放入全部的元素。請嘗試將兩個陣列merge成一個排序的陣列，
放置在第一個陣列中 。

由於最終要放在nums1裡，我們可以先考慮會有的情形：

n等於0：不用搬了，因為只有nums1有非0值。
m等於0：只要把nums2的全搬過來即可
其他：按照merge的原則，將雙方依序填入nums1中。

到這邊讀者可能會想到常規的merge是開一個新陣列 將雙方依次比較，
每次將較小的值放入新陣列，最後排序完成。
現在說想放到nums1當然是可以，但nums1前面有值 ，
直接這麼做會蓋掉耶！那怎麼辦呢？
答案很簡單，我們已經知道兩邊的長度是m跟n，
那麼合併後的長度就會是m+n ，尾端的index會是m+n-1 。
我們只要將**「每次將較小的值放入開頭」** 改成**「每次將較大的值放入結尾」** ，最後即可達到相同的狀況。

所以操作順序會是：

令i, j, k分別為m-1, n-1, m+n-1 2. 當i和j都≥0 時：
如果nums1的值比nums2的值大，
將nums1的尾端放到k的位置，同時遞減i跟k以更新。
如果nums1的值比nums2的值小(或相等)，
將nums2的尾端放到k的位置，同時遞減j跟k以更新。
重複這個迴圈直到跳出，代表有一邊陣列放完了 。
當 i ≥ 0 時，表示其實我們已經做完了，所以不用任何操作。
(剩下nums1前面的部分，不需要再動了)
當 j ≥ 0 時，表示 i 的部分已經被用完了，
剩下的就是一路將 j 的對應值填入即可。

Java的部分，可以利用**”–“** 讓對應index先填入以後再進行遞減，
步驟流程請參考上面演算方式並對照。

Java

Python沒有++或 – 這種東西，所以遞減時要乖乖的自己等於自己減一，
不過可以將需要遞減的寫在同一行，會稍微簡潔一點點。

Python

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(m+n)，O(1)
前者是典型merge的時間，後者是因為我們只有使用常數變數，
其他都是原有的記憶體空間，故僅額外占用到O(1)的空間)

相似及延伸

1.0021. Merge Two Sorted Lists (Easy) 2. 0148. Sort List (Medium)

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~