題目描述:給定兩個非遞減排序的整數陣列 nums1 和 nums2,以及兩個整數 m 和 n,分別代表 nums1 和 nums2 中有效元素的數量。nums1 的長度為 m + n,後 n 個位置為空(值為 0)。請將 nums2 合併到 nums1 中,使結果仍為非遞減排序。
解題思路:從後往前合併是關鍵。若從前往後合併,移動元素時會覆蓋 nums1 中尚未比較的值。改從尾端開始,使用三個指標:i 指向 nums1 有效元素末尾(m-1)、j 指向 nums2 末尾(n-1)、k 指向 nums1 整體末尾(m+n-1)。每次比較 nums1[i] 與 nums2[j],將較大者放到 nums1[k],並移動對應指標與 k。當 j < 0 時,nums2 已全部合入,剩餘 nums1 元素原地不動,無需再處理。若 i < 0,則將 nums2 剩餘元素直接複製到 nums1 前段。
時間複雜度:O(m + n) — 每個元素恰好被比較並放置一次,總共處理 m + n 個元素。
空間複雜度:O(1) — 所有操作都在 nums1 原地進行,只使用固定數量的指標變數,無需額外陣列。
1. Initialize three pointers: i = m-1 (end of nums1 valid part), j = n-1 (end of nums2), k = m+n-1 (end of nums1 total) 2. While both i >= 0 and j >= 0: a. If nums1[i] >= nums2[j], place nums1[i] at nums1[k], decrement i and k b. Else place nums2[j] at nums1[k], decrement j and k 3. While j >= 0 (remaining nums2 elements): a. Place nums2[j] at nums1[k], decrement j and k 4. Return (nums1 is now sorted in-place)
方法一:先合併再排序
將 nums2 的元素直接複製到 nums1 的後段(從索引 m 開始),然後對整個 nums1 呼叫 sort()。時間複雜度 O((m+n) log(m+n)),空間複雜度 O(1)(或 O(log(m+n)) 排序遞迴棧)。實作簡單但未利用已排序的特性,效率較差。
方法二:使用額外陣列(從前往後合併)
建立大小 m+n 的暫存陣列,以標準合併排序的合併步驟從前往後比較 nums1 和 nums2,將結果寫入暫存陣列,最後複製回 nums1。時間複雜度 O(m+n),空間複雜度 O(m+n)。雖然時間最優,但需要額外空間,不符合原地要求。
nums1 沒有預留額外空間,無法原地操作,你會如何設計一個 O(m+n) 時間、O(1) 空間的解法?