LeetCode | 189. 旋转数组 #83
Description
题目：
解法
解法1： 使用环状替换
结合这张图看
start 等于0也就是值为1开始， 1 ~ 3 ~ 5 ~ 1 ，3被1替换，5被3替换，1被5替换
跳到1的时候start === current，结束本次环状替换。(图中绿线)
start++，也就是start等于1值为2开始，2 ~ 4~ 6 ~ 2，4被2替换，6被4替换，2被6替换，跳到2的时候start === current，结束本次环状替换。(图中红线线)
一次类推不断进行下一个do while，直到count次数累计达到数组长度，说明数组每个数都挪好位置了。
/**
* @param {number[]} nums
* @param {number} k
* @return {void} Do not return anything, modify nums in-place instead.
*/
// k % nums.length 取移动k位置实际在nums中的位置。
// 声明count，count次数累计达到数组长度，说明数组每个数都挪好位置了。
// 进行start初始值为0，条件为count< nums.length的的for循环，
// current当前值为start值以及之后不断加k，直到current值再次等于本次循环的start值，
// 说明已经轮过一圈了，start值+1，然后跟着这个新的start值，不断加k，步骤如同上个循环。
var rotate = function(nums, k) {
const length = nums.length;
k = k % length;
let count = 0;
for(let start = 0; count < length; start ++) {
let current = start;
let pre = nums[start];
do {
const next = (current + k) % length;
const temp = nums[next];
nums[next] = pre;
current = next;
pre = temp;
count ++;
} while (current !== start);
}
};复杂度分析
时间复杂度：O(n) 。只遍历了每个元素一次。
空间复杂度：O(1) 。使用了常数个额外空间。
解法2：使用反转
原始数组 : 1 2 3 4 5 6 7
反转所有数字后 : 7 6 5 4 3 2 1
反转前 k 个数字后 : 5 6 7 4 3 2 1
反转后 n-k 个数字后 : 5 6 7 1 2 3 4 --> 结果
/**
* @param {number[]} nums
* @param {number} k
* @return {void} Do not return anything, modify nums in-place instead.
*/
// 整个数组反转
// 反转前k个数字
// 反转后n-k个数字
var rotate = function(nums, k) {
k %= nums.length;
reverse(nums, 0, nums.length-1);
reverse(nums, 0, k-1);
reverse(nums, k, nums.length-1);
};
function reverse(nums, start, end) {
while( start < end ) {
const temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start++;
end--;
}
} 时间复杂度：O(n)) 。 n 个元素被反转了总共 3 次。
空间复杂度：O(1) 。 没有使用额外的空间。