189. 旋转数组
给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
示例 1:
1
2
3
4
5
6
| 输入: [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]
|
示例 2:
1
2
3
4
5
| 输入: [-1,-100,3,99] 和 k = 2
输出: [3,99,-1,-100]
解释:
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]
|
思路：这道题虽然很简单，但是却有更加快速的操作。
就是先翻转整个数组，然后在要求的节点前后进行两次翻转。
举个栗子：
[1, 2, 3, 4, 5, 6, 7] k = 3
整个数组翻转：[7, 6, 5, 4, 3, 2, 1]
前半部分翻转：[5, 6, 7, 4, 3, 2, 1]
后半部分翻转：[5, 6, 7, 1, 2, 3, 4]
上Code：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
void rotate(vector<int>& nums, int k) {
if(nums.size() <= 1) {
return ;
}
int n = nums.size();
k %= nums.size();
for(int i = 0;i < n / 2;i++) {
swap(nums[i], nums[n - 1 - i]);
}
for(int i = 0;i < k / 2;i++) {
swap(nums[i], nums[k - i - 1]);
}
for(int i = k;i < (n + k) / 2;i++) {
swap(nums[i], nums[n - 1 - i + k]);
}
}
};
|