blob: 19f66dd0dc82015b6958695f708768abfad9e10a (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
class Solution {
public:
// Works, but it's slow.
/*int gcd(int a, int b) {
if (a == 0) return b;
if (b == 0) return a;
if (a == b) return a;
if (a > b) return gcd(a-b, b);
else return gcd(a, b-a);
}*/
// Much faster than the above implementation.
int gcd(int a, int b) {
if (b == 0) return a;
else return gcd(b, a%b);
}
void rotate(vector<int>& nums, int k) {
const size_t N = nums.size();
if ((N <= 1) || (k == 0)) {
return;
}
// Original algorithm only works for (N,k) coprime.
// Break the cycles when we complete a loop around the array.
const int gcdNk = gcd(N,k);
const int steps = (gcdNk != 1) ? (N / gcdNk) : N;
int start = -1;
for (size_t n = 0; n < N; n += steps) {
++start;
int i = start;
int i_val = nums[i];
for (size_t s = 0; s < steps; ++s) {
const int next = (i+k) % N;
std::swap(i_val, nums[next]);
i = next;
}
}
}
};
|
