從LeetCode學演算法 - 38 Array (7)
0088. Merge Sorted Array (Easy)
寫在前面： 如果覺得這篇有幫助到您的話， 請幫我隨手點開最下面的SHOW EMBED並拍5下手~ (當然，Medium的拍手也可以多拍幾下啦XD) 這樣我再寫個十多篇以後應該就有買一杯咖啡的$$了XDDDDD (聽起來超少哈哈)
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:
Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3Output: [1,2,2,3,5,6]分析/解題： 這題雖然相對比較無聊， 但merge的過程中其實蠻像merge sort的merge的， 所以選來讓讀者熟悉一下merge的概念，對上上篇提的應該會有幫助。
題目給定兩個陣列及有放元素的對應長度，兩者除了未放元素的0以外， 其他均已排序。同時，題目也假設第一個陣列必定有足夠空間， 可以放入全部的元素。請嘗試將兩個陣列merge成一個排序的陣列， 放置在第一個陣列中。
由於最終要放在nums1裡，我們可以先考慮會有的情形： 1. n等於0：不用搬了，因為只有nums1有非0值。 2. m等於0：只要把nums2的全搬過來即可 3. 其他：按照merge的原則，將雙方依序填入nums1中。
到這邊讀者可能會想到常規的merge是開一個新陣列將雙方依次比較， 每次將較小的值放入新陣列，最後排序完成。 現在說想放到nums1當然是可以，但nums1前面有值， 直接這麼做會蓋掉耶！那怎麼辦呢？ 答案很簡單，我們已經知道兩邊的長度是m跟n， 那麼合併後的長度就會是m+n，尾端的index會是m+n-1。 我們只要將「每次將較小的值放入開頭」改成「每次將較大的值放入結尾」，最後即可達到相同的狀況。
所以操作順序會是： 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以更新。 重複這個迴圈直到跳出，代表有一邊陣列放完了。
3. 當 i ≥ 0時，表示其實我們已經做完了，所以不用任何操作。 (剩下nums1前面的部分，不需要再動了)
4. 當 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學演算法，我們下次見囉，掰~
如果你／妳覺得這篇文章不錯，請給我5個拍手，並且給我5個Like。(點開SHOW EMBED!)
如果你／妳非常喜歡這篇文章，可以按著拍手直到50下。
也請記得「Follow」我，隨時收看最新的文章。
