题解 | #旋转数组#
旋转数组
https://www.nowcoder.com/practice/e19927a8fd5d477794dac67096862042
除了三次翻转以外的O(1)空间思路：一步旋转到位
如果m=1，用一个萝卜一个坑的想法，萝卜A移到B，B到C，最后一个萝卜放到A的坑，就结束了。可是m可能是任意值，一次循环做完不一定所有萝卜的坑位都换了，比如数组1-6要旋转2个单位，就会分别存在1 -> 3 -> 5 -> 1和2 -> 4 -> 6 -> 2的两个环。
既然可能存在多个环，那么不是可以像DFS算岛的数量一样，遍历完一个环就去下一个环吗？在岛屿遍历中，我们可以mark走过的点，但这题无法添加mark，而且只有O(1)空间所以也不能用额外的数据结构记录访问过的点。但这些环有一个性质，就是若存在多个环，那么每个环的起点是相邻的 (假设以0作为起点，若相邻的1也在同一个环内的话，说明在走了n圈之后，可以达到1，那么以此类推，再走n圈就能到达2。只要继续走，所有点都能在该环内遍历到)。所以只要知道环的数量，就可以顺序访问找到下一个环的一个点开始遍历。
环的数量是多少呢？我们知道一个环里是不可能有重复点的，且所有环的长度相同，所以环的数量为数字总数n除以一个环的长度length。
长度就很好计算了，先遍历一个环我们就知道环长了。最后实现代码如下：
import java.util.*;
public class Solution {
/**
* 旋转数组
* @param n int整型 数组长度
* @param m int整型 右移距离
* @param a int整型一维数组 给定数组
* @return int整型一维数组
*/
public int[] solve (int n, int m, int[] a) {
if ((m = m % n) == 0 || n < 2) {
return a;
}
int circleLen = rotate(a, 0, m, n);
int circleCount = n / circleLen;
for (int i = 1; i < circleCount; i++) {
rotate(a, i, m, n);
}
return a;
}
public int rotate(int[] a, int start, int m, int n) {
int circleLen = 1;
int cur = a[start];
int next = start + m, nextVal;
while (next != start) {
circleLen++; // 统计环的长度+1
nextVal = a[next]; // 把下一个数字B取出
a[next] = cur; // 当前数字A占领B的位置
cur = nextVal; // 拿着B
next = (next + m) % n; // 找下一个位置C
}
a[start] = cur; // 最后剩下的数字放回环的起点
return circleLen;
}
}
腾讯开奖369人在聊