Rotate Array : 給定一個數組,將數組向右旋轉 k 步,其中 k 是非負數
Python
方法一 :
- 先用 tmp 紀錄最後一段的數組切片(比方說上面那個例題,先用tmp紀錄[5, 6, 7])
- 將nums的第k項到最後一項用0到n-k項取代([4, 5, 6, 7]被[1, 2, 3, 4]取代)
- 最後再將tmp放回去 ([1, 2, 3]被[5, 6, 7]取代)。
class Solution:
def rotate(self, nums, k: int) -> None:
n = len(nums)
# k 取餘數,比方說等於n根本不用旋轉
k %= n
if k != 0:
# 1
tmp = nums[-k:]
# 2
nums[k:n] = nums[:n - k]
# 3
nums[0:k] = tmp
方法二 :
- 首先先將整個數組翻轉一次
- 接下來看k多少決定左邊以及右邊的分界
- 翻轉左邊,然後翻轉右邊
class Solution:
def rotate(self, nums, k: int) -> None:
k %= len(nums)
def reverse(nums, i, j):
while i < j:
nums[i], nums[j] = nums[j], nums[i]
i += 1
j -= 1
reverse(nums, 0, len(nums)-1)
reverse(nums, 0, k-1)
reverse(nums, k, len(nums)-1)
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() - k); // 翻轉前n-k個元素
reverse(nums.end() - k, nums.end()); // 翻轉後k個元素
reverse(nums.begin(), nums.end()); // 翻轉整個數組
}
};
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n = nums.size();
k = k % n; // 如果k大於n,取餘數,可以避免不必要的旋轉。
if (k == 0) return; // 特例,如果k為0,直接返回原數組。
int left = 0, right = n - 1;
while (left < right) { // 先翻轉整個數組
swap(nums[left], nums[right]);
left++;
right--;
}
left = 0;
right = k - 1;
while (left < right) { // 再翻轉前k個元素
swap(nums[left], nums[right]);
left++;
right--;
}
left = k;
right = n - 1;
while (left < right) { // 最後翻轉剩下的元素
swap(nums[left], nums[right]);
left++;
right--;
}
}
};