189. 旋轉數組（點擊查看題目）
題目描述
給定一個數組，將數組中的元素向右移動 k 個位置，其中 k 是非負數。
示例 1:
示例 2:
說明:
- 儘可能想出更多的解決方案，至少有三種不同的方法可以解決這個問題。
- 要求使用空間複雜度為 O(1) 的 原地 算法。
解決方案
方法 1：暴力
最簡單的方法是旋轉 k 次，每次將數組旋轉 1 個元素。
Java 實現
複雜度分析
- 時間複雜度：O(n*k)。每個元素都被移動 1 步（O(n)）k 次 (O(k))。
- 空間複雜度：O(1)。沒有額外空間被使用。
方法 2：使用額外的數組
算法
我們可以用一個額外的數組來將每個元素放到正確的位置上，也就是原本數組裡下標為 i 的我們把它放到 (i + k)% 數組長度的位置。然後把新的數組拷貝到原數組中。
Java 實現
複雜度分析
- 時間複雜度：O(n)。將數字放到新的數組中需要一遍遍歷，另一邊來把新數組的元素拷貝回原數組。
- 空間複雜度：O(n)。另一個數組需要原數組長度的空間。
方法 3：使用環狀替換
算法
如果我們直接把每一個數字放到它最後的位置，但這樣的後果是遺失原來的元素。因此，我們需要把被替換的數字保存在變量 temp 裡面。然後，我們將被替換數字 (temp) 放到它正確的位置，並繼續這個過程 n 次，n 是數組的長度。這是因為我們需要將數組裡所有的元素都移動。但是，這種方法可能會有個問題，如果 n %k == 0，其中 k = k%n（因為如果 k 大於 n，移動 k 次實際上相當移動 k%n 次）。這種情況下，我們會發現在沒有遍歷所有數字的情況下回到出發數字。此時，我們應該從下一個數字開始再重複相同的過程。
現在，我們看看上面方法的證明。假設，數組裡我們有 n 個元素並且 k 是要求移動的次數。更進一步，假設 n %k == 0。第一輪中，所有移動數字的下標 i 滿足 i%k == 0。這是因為我們每跳 k 步，我們只會到達相距為 k 個位置下標的數。每一輪，我們都會移動 n/k 個元素。下一輪中，我們會移動滿足 i%k == 1 的位置的數。這樣的輪次會一直持續到我們再次遇到 i%k == 0 的地方為止，此時 i = k 。此時在正確位置上的數字共有 k * n/k = n 個。因此所有數字都在正確位置上。
讓我們看一下接下來的例子，以更好地說明這個過程：
Java 實現
複雜度分析
- 時間複雜度：O(n)。只遍歷了每個元素一次。
- 空間複雜度：O(1)。使用了常數個額外空間。
方法 4：使用反轉
算法
這個方法基於這個事實：當我們旋轉數組 k 次， k%n 個尾部元素會被移動到頭部，剩下的元素會被向後移動。
在這個方法中，我們首先將所有元素反轉。然後反轉前 k 個元素，再反轉後面 n - k 個元素，就能得到想要的結果。
假設 n = 7 且 k = 3。
Java 實現
複雜度分析
- 時間複雜度：O(n)。n 個元素被反轉了總共 3 次。
- 空間複雜度：O(1)。沒有使用額外的空間。
閱讀更多 力扣LeetCode 的文章
