Rotate Array – LeetCode 189
Problem
Description
Rotate an array of n elements to the right by k steps.
Answer
Original
Code
1
2
3
4
5
6
7
8
9
10
| class Solution {
public:
void rotate(vector<int>& nums, int k) {
if(nums.empty() || (k %= nums.size()) == 0) return;
unsigned n = nums.size();
reverse(nums.begin(),nums.begin()+n-k);
reverse(nums.begin()+n-k,nums.end());
reverse(nums.begin(),nums.end());
}
};
|
思路
使用三次逆转来完成，总共需要两次遍历，时间复杂度$O(n)$，空间复杂度$O(1)$。
耗时$19$ ms，排名$58.54\%$
Better
思路
不断的将值进行偏移赋值，一次遍历即可。时间复杂度$O(n)$，空间复杂度$O(1)$。
耗时$19$ ms，排名$58.54\%$
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) {
k %= nums.size();
unsigned cnt = 0;
for(unsigned start = 0; cnt < nums.size(); ++start){
unsigned curr = start;
int prev = nums[start];
do {
unsigned next = (curr + k) % nums.size();
int tmp = nums[next];
nums[next] = prev;
prev = tmp;
curr = next;
++cnt;
} while(curr != start);
}
}
};
|