LeetCode189 Rotate Array

文章目录
  1. 1. 描述
  2. 2. 样例
  3. 3. 思路
  4. 4. 代码

描述

Rotate an array of n elements to the right by k steps.

样例

1
2
For example, with n = 7 and k = 3, 
the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

思路

将数组中每个元素循环右移k位。

不妨记A = [1, 2, 3, 4],B = [5, 6, 7],其目标就是是将原数组从 AB 变成 BA,所以可以运用$BA = (A^TB^T)^T$这一性质。注:$A^T$的意思是将数组$A$中元素翻转。

leetCode189

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
void reverse(vector<int>& nums, int l, int r) {
while (l < r) swap(nums[l++], nums[r--]);
}
void rotate(vector<int>& nums, int k) {
int n = nums.size();
k %= n; // 去掉无意义的移动
reverse(nums, 0, n - k - 1);
reverse(nums, n - k, n - 1);
reverse(nums, 0, n - 1);
}
};
分享到 评论