給定整數陣列
nums，將陣列向右旋轉k步。
Example:
Input: nums = [1,2,3,4,5,6,7], k = 3 Output: [5,6,7,1,2,3,4]
Intuition
TIP
核心思路：三次反轉法 — 先全部反轉，再分別反轉前 k 個和後 n-k 個。
- 旋轉 k 步 = 把最後 k 個元素搬到最前面
- 三次反轉可以巧妙地達成這個效果：
- 全部反轉：
[7,6,5,4,3,2,1] - 反轉前 k 個：
[5,6,7,4,3,2,1] - 反轉後 n-k 個：
[5,6,7,1,2,3,4]
- 全部反轉：
- 記得先對 k 取模，避免 k > n 的情況
Approaches
1. Extra Array — O(n) / O(n)
- Idea: 建立新陣列，把每個元素放到
(i + k) % n的位置 - Time:
O(n) - Space:
O(n)- 額外陣列
class Solution {
fun rotate(nums: IntArray, k: Int): Unit {
val n = nums.size
val result = IntArray(n)
for (i in nums.indices) {
result[(i + k) % n] = nums[i]
}
for (i in nums.indices) nums[i] = result[i]
}
}⭐ 2. Three Reversals — O(n) / O(1)
- Idea: 全部反轉 -> 反轉前 k 個 -> 反轉後 n-k 個
- Time:
O(n)- 三次線性掃描 - Space:
O(1)- 原地操作
class Solution {
fun rotate(nums: IntArray, k: Int): Unit {
val n = nums.size
val step = k % n
reverse(nums, 0, n - 1)
reverse(nums, 0, step - 1)
reverse(nums, step, n - 1)
}
private fun reverse(nums: IntArray, start: Int, end: Int) {
var left = start
var right = end
while (left < right) {
val temp = nums[left]
nums[left] = nums[right]
nums[right] = temp
left++
right--
}
}
}WARNING
務必先 k % n，否則 k >= n 時反轉範圍會出錯。當 step == 0 時不需任何操作。
🔑 Takeaways
- Pattern: 三次反轉法（Reverse Three Times）是陣列旋轉的經典 O(1) 空間做法
- Key trick: 反轉子陣列是 Two Pointers 的基本操作；此方法也適用於字串旋轉問題