Problem: 189. 輪轉數組
題目：給定一個整數數組 nums，將數組中的元素向右輪轉 k 個位置，其中 k 是非負數。
文章目錄
- 整體思路
- 完整代碼
- 時空復雜度
- 時間復雜度：O(N)
- 空間復雜度：O(N)
整體思路
這段代碼旨在解決一個經典的數組問題：旋轉數組 (Rotate Array)。問題要求將一個數組中的元素向右循環移動 k 個位置。例如，將 [1, 2, 3, 4, 5] 向右移動 2 位，結果應為 [4, 5, 1, 2, 3]。
該實現采用了一種非常直觀的方法：使用一個額外的數組來輔助完成旋轉。其邏輯步驟清晰明了：
-
處理
k值：- 首先，代碼對
k進行了取模運算k = k % n。這是非常重要的一步，因為如果k大于數組長度n，旋轉k位和旋轉k % n位的效果是完全相同的。例如，旋轉n位等于沒有旋轉。這可以處理k為任意非負整數的情況。
- 首先，代碼對
-
創建輔助數組：
- 創建一個與原數組
nums等長的新數組ans。這個數組將用來臨時存放旋轉后的結果。
- 創建一個與原數組
-
構建旋轉后的數組：
- 算法將原數組
nums分為兩部分來處理：
a. 后k個元素：這部分元素在旋轉后會移動到新數組的開頭。代碼通過for (int i = n - k; i < n; i++)循環，將nums的后k個元素（從索引n-k到n-1）依次復制到ans數組的開頭（從索引0開始）。
b. 前n-k個元素：這部分元素在旋轉后會緊跟在上面那部分元素的后面。代碼通過for (int i = 0; i < n - k; i++)循環，將nums的前n-k個元素（從索引0到n-k-1）依次復制到ans數組的剩余位置。 - 一個
cur指針被用來無縫地追蹤ans數組中下一個要填充的位置。
- 算法將原數組
-
將結果復制回原數組：
- 當
ans數組完全構建好后，它里面就存儲了正確的旋轉結果。 - 最后，通過一個循環
for (int i = 0; i < n; i++)，將ans數組中的所有元素逐一復制回原數組nums中，以滿足題目通常要求的“原地修改”。
- 當
總而言之，這是一個邏輯簡單、易于理解但空間效率不高的解法。
完整代碼
class Solution {/*** 將數組 nums 的元素向右循環移動 k 個位置。* @param nums 要旋轉的整數數組* @param k 非負整數，表示移動的位數*/public void rotate(int[] nums, int k) {// 獲取數組的長度int n = nums.length;// 創建一個等長的輔助數組 ans，用于存儲旋轉后的結果int[] ans = new int[n];// cur 指針，用于追蹤在 ans 數組中當前要填充的索引位置int cur = 0;// 步驟 1: 對 k 取模，處理 k >= n 的情況。// 旋轉 k 位和旋轉 k % n 位的效果是一樣的。k = k % n;// 步驟 2: 將原數組的后 k 個元素復制到新數組的開頭// 這部分元素是從索引 n-k 到 n-1for (int i = n - k; i < n; i++) {ans[cur++] = nums[i];}// 步驟 3: 將原數組的前 n-k 個元素復制到新數組的剩余位置// 這部分元素是從索引 0 到 n-k-1for (int i = 0; i < n - k; i++) {ans[cur++] = nums[i];}// 步驟 4: 將新數組 ans 的內容復制回原數組 nums// 以滿足原地修改的要求for (int i = 0; i < n; i++) {nums[i] = ans[i];}}
}
時空復雜度
時間復雜度：O(N)
- 取模運算：
k = k % n是 O(1) 操作。 - 第一個復制循環：
for (int i = n - k; i < n; i++)執行k次。 - 第二個復制循環：
for (int i = 0; i < n - k; i++)執行n-k次。- 這兩個循環合起來，總共對
nums數組進行了一次完整的遍歷，將元素復制到ans。總操作次數是k + (n-k) = n。
- 這兩個循環合起來，總共對
- 第三個復制循環：
for (int i = 0; i < n; i++)執行n次，將ans的內容復制回nums。 - 綜合分析：
- 算法總共執行了大約
n + n = 2n次的元素復制操作。 - 因此，總的時間復雜度是線性的，即 O(N)。
- 算法總共執行了大約
空間復雜度：O(N)
- 主要存儲開銷：算法創建了一個名為
ans的整型數組來作為輔助存儲空間。 - 空間大小：該數組的長度與輸入數組
nums的長度N相同。 - 其他變量：
n,cur,k,i等變量都只占用常數級別的空間，即 O(1)。
綜合分析：
算法所需的額外空間主要由輔助數組 ans 決定。因此，其空間復雜度為 O(N)。這是一個非原地（not-in-place）的算法。
【LeetCode 熱題 100】189. 輪轉數組——（解法二）反轉數組
