LeetCode 189. Rotate Array
Given an array, rotate the array to the right by k
steps, where k is non-negative.
Example 1:
Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]
method 1: 额外的数组
把nums[i]
赋值到移动后的位置,注意取模
void rotate(vector<int>& nums, int k) {
int n = nums.size();
vector<int> res(n);
for (int i = 0; i < n; i++) {
res[(i + k) % n] = nums[i];
}
nums.swap(res);
}
时间复杂度:$O(n)$
空间复杂度:$O(n)$
method 2: 原地翻转
void swap(vector<int>& nums, int i, int j) {
while (i < j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
i++, j--;
}
}
void rotate(vector<int>& nums, int k) {
int n = nums.size();
k %= n;
swap(nums, 0, n - 1); // 1
swap(nums, 0, k - 1); // 2
swap(nums, k, n - 1); // 3
}