問題描述
給定長度為 n 的陣列 nums，將陣列中的元素向右旋轉 k 個位置，其中 k 是非負數。
輸入: nums = [1,2,3,4,5,6,7], k = 3
輸出: [5,6,7,1,2,3,4]
解釋:
向右旋轉 1 步: [7,1,2,3,4,5,6]
向右旋轉 2 步: [6,7,1,2,3,4,5]
向右旋轉 3 步: [5,6,7,1,2,3,4]
解法一：使用額外陣列的直觀解法
直觀的想法是使用一個額外的陣列，將旋轉後的位置預先計算好，然後將元素放在正確的位置。
時間複雜度：O(n)
因為需要遍歷整個陣列一次。
C++程式碼：
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n = nums.size();
vector<int> temp(n); // 建立臨時陣列
k = k % n; // 處理 k 大於 n 的情況
for(int i = 0; i < n; i++) {
temp[(i + k) % n] = nums[i]; // 計算新位置並賦值
}
nums = move(temp); // 將結果移回原陣列
}
};
解釋：
- 創建一個與原陣列大小相同的臨時陣列
temp。 - 遍歷原陣列，計算每個元素在旋轉後的位置
(i + k) % n，並將元素放入temp中的對應位置。 - 將
temp中的元素移回原陣列nums。
解法二：反轉
為了減少空間複雜度，我們可以考慮在原陣列上進行操作，不使用額外的空間。核心思想是通過反轉陣列來達到旋轉的效果。
時間複雜度：O(n)
反轉操作需要遍歷陣列，但總共只遍歷了 3 次。
C++程式碼：
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n = nums.size();
k = k % n; // 處理 k 大於 n 的情況
reverse(nums.begin(), nums.end()); // 整體反轉
reverse(nums.begin(), nums.begin() + k); // 反轉前 k 個元素
reverse(nums.begin() + k, nums.end()); // 反轉後 n - k 個元素
}
};
解釋：
- 整體反轉陣列： 將陣列的所有元素反轉，這樣原本的順序被顛倒。
- 反轉前 k 個元素： 將陣列的前 k 個元素再次反轉，使其回到正確的順序。
- 反轉後 n - k 個元素： 將剩下的元素（從第 k 個位置到結尾）反轉，恢復正確順序。
步驟拆分：
以陣列 [1,2,3,4,5,6,7] 和 k = 3 為例：
- 整體反轉：
複製程式碼原陣列：1 2 3 4 5 6 7
反轉後：7 6 5 4 3 2 1 - 反轉前 k 個元素（前 3 個）：
複製程式碼部分反轉：5 6 7 | 4 3 2 1
- 反轉後 n - k 個元素（後 4 個）：
複製程式碼最終結果：5 6 7 1 2 3 4
以上是 Hua 在 LeetCode 的解題分享，有想法或是建議歡迎在底下討論。
Day Day Good, Day Day Up !