189. Rotate Array

Given an array, rotate the array to the right by k steps, where k is non-negative.

环型替换,先求出数列长度和轮转次数的最大公约数m。
然后依次替换数列中的每个值。

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
40
41
42
43
44
45
//Rotate Array

class Solution {
public void rotate(int[] nums, int k) {
if (k != 0){
int m = gcd(nums.length,k);

for (int n = 0; n < m; n++ ) {
int i = n + k;
i %= nums.length;

int temp = nums[n];
while( true ){
int tempI = nums[i];
nums[i] = temp;
temp = tempI;

i += k;
i %= nums.length;

if (i == n){
nums[n] = temp;
break;
}
}
}
}
}

private int gcd(int a, int b){
int max = a;
int min = b;
if (max == min){
return min;
}

if ( a < b ){
max = b;
min = a;
}

return gcd(max - min, min);
}
}

Author

Xander

Posted on

2022-04-03

Updated on

2022-04-20

Licensed under

Comments