![Leetcode|取余+数组翻转|189. 旋转数组 Leetcode|取余+数组翻转|189. 旋转数组](/default/index/img?u=aHR0cHM6Ly93d3cuaWNvZGU5LmNvbS9pL2xsLz9pPWNlZTIyOTlkYmMwYzQyZTY5YmNjN2YzOGI5Y2Q2N2JiLnBuZz8sdHlwZV9abUZ1WjNwb1pXNW5hR1ZwZEdrLHNoYWRvd18xMCx0ZXh0X2FIUjBjSE02THk5aWJHOW5MbU56Wkc0dWJtVjBMMU5NWDFkdmNteGssc2l6ZV8xNixjb2xvcl9GRkZGRkYsdF83MA==)
1 数组翻转—
O
(
1
)
O(1)
O(1)空间复杂度,
O
(
n
)
O(n)
O(n)时间复杂度
![Leetcode|取余+数组翻转|189. 旋转数组 Leetcode|取余+数组翻转|189. 旋转数组](/default/index/img?u=aHR0cHM6Ly93d3cuaWNvZGU5LmNvbS9pL2xsLz9pPThiYzk5MzE5ODZlZTRhYTNhZGIyMzU4ZDViODI0ZDdiLnBuZz8sdHlwZV9abUZ1WjNwb1pXNW5hR1ZwZEdrLHNoYWRvd18xMCx0ZXh0X2FIUjBjSE02THk5aWJHOW5MbU56Wkc0dWJtVjBMMU5NWDFkdmNteGssc2l6ZV8xNixjb2xvcl9GRkZGRkYsdF83MA==)
class Solution {
public:
void reverse(vector<int>& nums, int left, int right) {
while (left < right) {
swap(nums[left], nums[right]);
left++; right--;
}
}
void rotate(vector<int>& nums, int k) {
int size = nums.size();
// 1.翻转全部数组,将后k个元素翻转到前面
reverse(nums, 0, size - 1);
// 2.翻转前(k % size)元素,保证排序
reverse(nums, 0, (k % size) - 1);
// 2.翻转后size - (k % size)元素
reverse(nums, (k % size), size - 1);
}
};
![Leetcode|取余+数组翻转|189. 旋转数组 Leetcode|取余+数组翻转|189. 旋转数组](/default/index/img?u=aHR0cHM6Ly93d3cuaWNvZGU5LmNvbS9pL2xsLz9pPWZiMmZhOWFiODg4OTQzOTZiYTA1ZjVmOGIzNjM2ZGY3LnBuZz8sdHlwZV9abUZ1WjNwb1pXNW5hR1ZwZEdrLHNoYWRvd18xMCx0ZXh0X2FIUjBjSE02THk5aWJHOW5MbU56Wkc0dWJtVjBMMU5NWDFkdmNteGssc2l6ZV8xNixjb2xvcl9GRkZGRkYsdF83MA==)
2 开辟额外数组—
O
(
n
)
O(n)
O(n)空间复杂度,
O
(
n
)
O(n)
O(n)时间复杂度
class Solution {
public:
void rotate(vector<int>& nums, int k) {
vector<int> res;
int size = nums.size();
// 后k个元素添加
for (int i = size - (k % size); i < size; i++)
res.emplace_back(nums[i]);
// 前size - k个元素添加
for (int i = 0; i < size - (k % size); i++)
res.emplace_back(nums[i]);
nums = res;
}
};