Leetcode 189: 輪轉數組

這是一道經典問題，題目要求將一個數組向右輪轉 k 個位置，有多種解法可以快速求解，既可以通過額外空間，也可以在 O(1) 的空間復雜度內完成。本題考察數組操作、雙指針，以及算法優化能力。

---

題目描述

輸入：

• 一個整數數組 nums
• 一個整數 k（表示右移的次數）。

輸出：

• 將數組元素旋轉 k 次后直接修改原數組，不返回值。

---

示例輸入輸出：

輸入：nums = [1,2,3,4,5,6,7], k = 3
輸出：[5,6,7,1,2,3,4]輸入：nums = [-1,-100,3,99], k = 2
輸出：[3,99,-1,-100]

---

解法 1：額外數組輔助

思路

1. 使用一個額外的數組 temp 來保存最終的旋轉結果。
2. 拷貝操作：
   • 遍歷原數組，將 nums[i] 放置到新位置 (i + k) % n 中。
3. 覆蓋結果：
   • 將 temp 中的內容轉存回原數組。

---

代碼模板

class Solution {public void rotate(int[] nums, int k) {int n = nums.length;k %= n; // 如果 k 大于數組長度，需要取模int[] temp = new int[n];for (int i = 0; i < n; i++) {temp[(i + k) % n] = nums[i]; // 按照旋轉后的位置存儲}// 將 temp 的內容拷貝到原數組for (int i = 0; i < n; i++) {nums[i] = temp[i];}}
}

---

復雜度分析

• 時間復雜度：O(n)
  • 遍歷數組兩次，一次構造 temp 數組，一次拷貝回原數組。
• 空間復雜度：O(n)
  • 需要一個額外大小為 n 的數組存放臨時結果。

---

解法 2：環狀替換

思路

1. 核心觀察：
   • 通過旋轉，數組中的每個元素其實沿著環狀路徑被移動，例如第 i 個元素移動到位置 (i + k) % n。
   • 從某個點出發，將該點開始的所有元素按照這種環狀方式重新排列。
   • 當訪問過的元素數量達到數組大小 n 時，正好完成所有元素的輪轉。
2. 實現步驟：
   • 統計當前訪問過的元素數量 count，從未訪問過的某個起始點出發進行 “環繞替換”。
   • 對于每個元素，將其移至新位置 (i + k) % n，直到形成一個環，然后跳到下一個未訪問的點。

---

代碼模板

class Solution {public void rotate(int[] nums, int k) {int n = nums.length;k %= n; // 如果 k 大于數組長度，取模去掉多余輪轉int count = 0; // 記錄訪問的元素數量for (int start = 0; count < n; start++) { // 從未訪問的點開始int current = start; // 當前節點int prev = nums[start]; // 保存當前值do {int next = (current + k) % n; // 下一個位置int temp = nums[next]; // 保存下個位置的值nums[next] = prev; // 替換值prev = temp; // 更新 "前一個值"current = next; // 跳到下一個位置count++; // 更新訪問數量} while (current != start); // 環繞回起點時退出}}
}

---

復雜度分析

• 時間復雜度：O(n)
  • 每個元素最多被訪問一次。
• 空間復雜度：O(1)
  • 沒有使用額外數據結構，原地旋轉。

---

解法 3：數組翻轉技巧

思路

1. 數組輪轉可以通過 三步翻轉 實現：
   • 第 1 步：翻轉整個數組；
   • 第 2 步：翻轉前 k 個元素；
   • 第 3 步：翻轉后 n-k 個元素。
2. 實現原理：
   • 經過數組翻轉操作后，元素將被正確排列。
   • 例如：對于輸入 nums = [1,2,3,4,5,6,7], k=3：

     原始： [1, 2, 3, 4, 5, 6, 7]
     步驟 1 翻轉整個數組： [7, 6, 5, 4, 3, 2, 1]
     步驟 2 翻轉前 k 個元素：[5, 6, 7, 4, 3, 2, 1]
     步驟 3 翻轉后 n-k 個元素：[5, 6, 7, 1, 2, 3, 4]
     

---

代碼模板

class Solution {public void rotate(int[] nums, int k) {int n = nums.length;k %= n; // 如果 k 大于數組長度，取模處理// 翻轉函數reverse(nums, 0, n - 1); // 翻轉整個數組reverse(nums, 0, k - 1); // 翻轉前 k 個元素reverse(nums, k, n - 1); // 翻轉后 n-k 個元素}private void reverse(int[] nums, int start, int end) {while (start < end) {int temp = nums[start];nums[start] = nums[end];nums[end] = temp;start++;end--;}}
}

---

復雜度分析

• 時間復雜度：O(n)
  • 翻轉整個數組花費 O(n)，翻轉前后兩部分各花費 O(k) 和 O(n-k)，總時間為 O(n)。
• 空間復雜度：O(1)
  • 翻轉操作原地完成，沒有額外數據結構。

---

解法 4：雙指針 + 循環節

思路

• 使用雙指針從兩端到中間進行元素篩選調整。
• 或者結合環狀數組的位置動態安排記錄。

---

---

總結：如何快速 AC？

1. 優先選擇三步翻轉解法：O(n) 時間復雜度，O(1) 空間復雜度，實現簡單，效率最高，是面試中優先推薦的解法。
2. 針對特殊場景：
   • 如果原數組不可修改，可以選擇額外數組解法。
   • 如果需要一定技巧性（如比特運算分析競賽題），環狀替換法更具邏輯挑戰。
3. 邊界情況注意：
   • k 大于數組長度時，需要取模：k %= n。
   • 空數組或 k=0 時，直接返回。

通過掌握以上 3 種高效解法（特別是三步翻轉技巧），不僅可以輕松解決問題，還能給面試官留下深刻印象。