Leetcode — 88. Merge Sorted Array (中文)

問題連結: https://leetcode.com/problems/merge-sorted-array/

給兩個已排序好的陣列nums1 和nums2, 把nums2 併入nums1成一個"新的"排序陣列
題目也會給兩個變數m 和n 各代表nums1 和nums2的長度

⚠️一開始nums1給的長度就是 m+n, 代表有足夠空間去裝我們併進來的nums2

一些條件:

• 0 <= n, m <= 200
• 1 <= n + m <= 200
• nums1.length == m + n
• nums2.length == n
• -109 <= nums1[i], nums2[i] <= 109

範例 - 
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. 也就是不要再另外多創造一個array, 全部都在nums1裡面做排序

如果我們被允許可以多創造一個array, 整個問題就簡單多了
我們只要一直比較nums1跟nums2的大小 把小的放進新的陣列 然後繼續比較 就可以了 (典型的merge sort)
像這樣—

        int m = arr1.length, n = arr2.length;
        int i = 0, j = 0;
        int[] rst = new int[m+n];
        int k = 0;
        while(i<m && j<n)
        {
            if(arr1[i]<=arr2[j])
                rst[k++] = arr1[i++];
            else
                rst[k++] = arr2[j++];
        }
        while(i<m)
            rst[k++] = arr1[i++];
        while(j<n)
            rst[k++] = arr2[j++];
        return rst;

但如果要做到in-place, 我想的到兩種方法, 但都不會是最佳解

其中一種就是直接把nums2裡面的所有數字放進nums1的最後面, 再進行排序但這樣就跟merge sort完全沒關係 而且nums1 跟 nums2 已排序好了, 我們卻完全打亂 這個算是有用的笨方法

另一種就是 像上面的code一樣, 一直比較nums1和nums2的數字
但這個方法只有當nums1的所有數字都比nums2還小的時候才會成功, 不然nums1的有些數字都會被nums2蓋過
因此我們也需要想 要如何處理 會被新加的數字蓋過的nums1
如果當nums1要被蓋過, 把整個nums1還沒檢查過的數字全體往後移 時間複雜度又非常高 也不是個最佳解

在思考要怎麼處理 會被蓋過去的數字的時候我就想到, nums1有沒有數字我們蓋過去也沒差的? 沒錯, 就是一開始nums1尾部的那些0

與其從頭開始比較nums1和nums2, 不如倒過來放 我們從nums1的尾巴來放在nums1和nums2目前最大的數字, 然後一直往前放

(這時候就不用擔心會不會蓋過重要的數字了, 因為當我們要開始蓋nums1中重要的數字時,我們早已用過那些數字了)

我用一系列的圖來解釋我們如何不蓋過任何重要數字

👉Goal: Merge [2,4,5,0,0,0] and [1,2,3] when m = 3, n = 3

Step 1. 最一開始的狀態
i 跟 j 各指著nums1和nums2的最尾數字. k 可以想成我們"新陣列"的pointer, 指著我們正要assign的位置

1. 三個pointers在還沒開始時的最初狀態

Step 2. nums1[i] > nums2[j], 所以新陣列的第k位置就是 nums1[i]
i和k因為做完動作, 所以往前移一格, j則留原地

step 2 result

Step 3. nums1[i] > nums2[j], 所以新陣列的第k位置就是 nums1[i]
i和k因為做完動作, 所以往前移一格, j則留原地

step 3 result

Step 4. nums2[j] > nums1[i], 所以新陣列的第k位置就是 nums2[j]
j和k因為做完動作, 所以往前移一格, i則留原地

step 4 result

Step 5. 因為nums1[i]的值與nums2[j]相同 我們可以選i或j, 主要是看我們演算法怎麼寫. 這裡我們選擇把nums2[j]給新陣列的第k位
j和k因為做完動作, 所以往前移一格, i則留原地

step 5 result

⚠️有一件事情發生了 - 我們第一次覆蓋了我們nums1的數字!
但其實不用緊張, 我們蓋掉的是我們在前面就用過的數字了 原本的數字早就放進我們的"新陣列"裡

Step 6. nums1[i] > nums2[j], 所以新陣列的第k位置就是 nums1[i]
i和k因為做完動作, 所以往前移一格, j則留原地

step 6 result

Step 7. 到這裡時 因為i已經指著陣列外, 代表我們已經不能比較nums1[i]和nums2[j] 了 我們剩下的動作就是把還沒跑完的陣列剩下的elements全部都給"新陣列"nums1

Final Merged Array

以下為0ms程式碼, 贏過 100% :

public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m-1, j = n-1;
        int k = m+n-1;
        while(i>=0 && j>=0)
        {
            if(nums1[i] > nums2[j])
                nums1[k--] = nums1[i--];
            else
                nums1[k--] = nums2[j--];
        }
        while(i>=0)
            nums1[k--] = nums1[i--];
        while(j>=0)
            nums1[k--] = nums2[j--];
    }

我們甚至可以在上述程式碼中略過下面的loop
因為當我們i還大於等於0時, 代表k跟i指著nums1中同個位置的數字 (可以試著自己跑跑看 把[4,5,6]併入[1,2,3,0,0,0] 來看為何我們可以省這一步):

while(i>=0)
    nums1[k--] = nums1[i--];

時間複雜度: O(n)
空間複雜度: O(1)