雙指標法

解題思路

1. 初始化兩個指標：我們為兩個陣列 nums1 和 nums2 分別宣告一個指標，分別命名為 i 和 j。這兩個指標都會從各自陣列的起始位置開始。
2. 比較並選擇較小的數字：在每一次迭代中，我們會比較目前 i 和 j 指向的兩個數字，並將較小的數字加到結果中。
3. 移動指標：加完較小的數字後，我們會移動指向較小數字的指標到下一個位置。

重複步驟 2 和 3，直到其中一個陣列被完全搬完。然後，我們將另一個還沒被遍歷完的陣列的剩餘部分加到結果中。

透過以上步驟，我們就能有效地利用兩個陣列已排序的特性，並使用雙指標法來解決這個問題。

別閉門造車，一起準備面試吧！
在紙上呈現100%完美的你！打爆天下無敵手的履歷怎麼寫？找工作前的第一步：履歷健檢！
我們將幫助您撰寫一份出色的履歷表，讓您在眾多求職者中脫穎而出。我們將為您提供專業的建議和指導，幫助您在履歷上呈現最完美的自己。如果心動的話，就別猶豫啦！趕快把握機會，動動手指投遞履歷吧！立即加入 Line 讀書會，和大家一起實現夢想！

履歷諮詢	加入讀書會 (邀請碼：4372)

程式

class Solution {
    fun merge(nums1: IntArray, m: Int, nums2: IntArray, n: Int): Unit {
        val L = IntArray(m+1)
        for (i in 0 until m)
            L[i] = nums1[i]
        L[m] = Int.MAX_VALUE

        val R = IntArray(n+1)
        for (i in 0 until n)
            R[i] = nums2[i]
        R[n] = Int.MAX_VALUE
        
        var i=0
        var j =0

        for(k in 0 until m+n){
            if(L[i] <= R[j]){
                nums1[k] = L[i]
                i++
            }
            else {
                nums1[k] = R[j]
                j++
            }
        }
    }
}

複雜度分析

• 時間複雜度:
  。這是因為我們的演算法中有兩個指標，這兩個指標會在兩個陣列中移動。在最壞的情況下，這兩個指標可能需要移動 次，其中 和 分別是兩個陣列的長度。因此，我們的算法的時間複雜度是 。

• 空間複雜度:
  。這是因為我們需要將 nums1 和 nums2 分別複製到新的陣列 L 和 R 來存儲排序前的結果，兩個陣列的長度加起來會是 。因此，空間複雜度是 。

　更多演算法題解，一起來學習！

別閉門造車，一起準備面試吧！

在紙上呈現100%完美的你！打爆天下無敵手的履歷怎麼寫？找工作前的第一步：履歷健檢！

履歷諮詢	加入讀書會 (邀請碼：4372)