題目描述:給定一個整數陣列 nums 和一個非負整數 k,要求將陣列向右旋轉 k 步(in-place,O(1) 額外空間)。向右旋轉 k 步意味著原本在索引 i 的元素,會移動到索引 (i + k) % n 的位置。
解題思路:使用「三次反轉」技巧(Three-Reverse Trick),是解決此問題最優雅的 O(1) 空間方法。首先將 k 取模(k = k % n)以處理 k ≥ n 的情況。接著執行三個步驟:第一步反轉整個陣列;第二步反轉前 k 個元素;第三步反轉剩餘的 n-k 個元素。這三步操作後,元素的位置恰好等同於向右旋轉 k 步的結果。可以用小例子驗證:陣列 [1,2,3,4,5],k=2,反轉全部得 [5,4,3,2,1],反轉前 2 個得 [4,5,3,2,1],反轉後 3 個得 [4,5,1,2,3],正確。
時間複雜度:O(n) — 三次反轉分別遍歷陣列的不同區段,合計每個元素被訪問常數次,總體為 O(n)。
空間複雜度:O(1) — 所有反轉皆就地進行,使用 swap 交換元素,只需要有限個輔助變數,不需要額外陣列。
1. Compute k = k % n to handle cases where k >= n 2. If k == 0, return early (no rotation needed) 3. Reverse the entire array nums[0..n-1] 4. Reverse the first k elements nums[0..k-1] 5. Reverse the remaining elements nums[k..n-1] 6. The array is now rotated right by k positions Intuition: reversing all elements places each element at its "mirrored" position. Reversing the two halves individually then corrects their internal order.
方法一:使用額外陣列暫存 時間複雜度:O(n),空間複雜度:O(n) — 建立一個同等大小的輔助陣列,將 nums[i] 放置到新陣列的 (i+k)%n 位置,再複製回原陣列。邏輯最直觀,但需要 O(n) 額外空間,不符合題目最優空間要求。
方法二:環狀替換(Cyclic Replacement) 時間複雜度:O(n),空間複雜度:O(1) — 從位置 0 出發,將 nums[0] 放到 nums[k%n],再將被替換的值放到下一個目標位置,依此形成環狀鏈。若環未遍歷所有元素(發生在 n 與 k 的 gcd > 1 時),需從下一個起始位置重新出發。實作較複雜,需追蹤已替換元素數量。
方法三:逐步旋轉一步(暴力法) 時間複雜度:O(n*k),空間複雜度:O(1) — 每次只旋轉一步(將最後元素移到最前),重複 k 次。k 較大時(如 k 接近 n)效能較差,但在 k 很小時可接受。