题解 | #旋转数组#
旋转数组
http://www.nowcoder.com/practice/e19927a8fd5d477794dac67096862042
循环移位法
一位覆盖一位的挪动，例如将第 i 位 移动到 i + m 的位置上：
①先记录 i + m 位置上的数
tmp = a[i + m];②用 i 位置上的数覆盖 i + m 位置上的数
a[(i + m) % n] = a[i];③更新 i 为 i - m， 即 使用 i - m位置的数来覆盖 位置 i 的数
i = (idx - m + n) % n;重复②、③ n 次。
移动过程中可能出现循环移位问题
class Solution {
public:
vector<int> solve(int n, int m, vector<int>& a) { // 循环移位法
m = m % n;
if(!m) return a; // 如果 m = 0， 直接返回
int i, idx, tmp, cnt;
i = 0; // 从 第一个数开始右移
idx = (i + m) % n, tmp = a[idx]; // idx 位置的数将被 位置 i 的数覆盖，先用tmp记下来
cnt = n; // 一共需要移动 n 次
while(cnt --){
if(i == idx){ // 移到了 idx 位置，idx位置的数记录在tmp中
a[(i + m) % n] = tmp;
idx ++; // 继续移动会出现死循环的现象，由于当前移动过的两个数之间是等间隔的(m - 1)，所以让idx + 1，直到移动 n 次结束
i = (idx - m + n) % n;
tmp = a[idx];
continue;
}
a[(i + m) % n] = a[i];
i = (i - m + n) % n;
}
return a;
}
};
投递BOSS直聘等公司6个岗位