189.旋转数组.md

LeetCode 189.旋转数组

描述

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

示例 1:

输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]

示例 2:

输入: [-1,-100,3,99] 和 k = 2
输出: [3,99,-1,-100]
解释: 
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]

说明:

• 尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
• 要求使用空间复杂度为 O(1) 的 原地 算法。

解一 [暴力解法]

思路

每一次往右移动一个元素

代码

var rotate = function(nums, k) {
    let len = nums.length;
    while(k--){
        let temp = nums[len-1]
        for(let i = len-1; i; i--) {
            nums[i] = nums[i-1];
        }
        nums[0] = temp;
    }
    return nums;
};

解二 [借用额外数组]

思路

用一个新数组存放正确的位置 之后在把值赋给 nums

代码

var rotate = function(nums, k) {
    let arr = [], len = nums.length;
    for(let i = 0; i < len; i++) {
        arr[(i+k)%len] = nums[i]; // (i+k)%len 即如果i+k 小于len 则使用i+k当作索引 如果大于获等于len 则用余数当作索引即右侧要移动到左侧的部分
    }
    for(let j = 0; j < len; j++) {
        nums[j] = arr[j];
    }
    return nums;
};

解三 [反转]

思路

例：nums = [1,2,3,4,5,6,7] k = 3

1. 首先对nums反转一次 => [7,6,5,4,3,2,1]
2. 再对 nums[0] - nums[k] 和 nums[k] - nums[nums.length] 分别反转一次 => [5,6,7,1,2,3,4] 代码

var rotate = function(nums, k) {
    // 反转整个数组
    nums.reverse();
    let len = nums.length;
    k %= len;
    let leftLen = k >> 1, rightLen = (len - k) >> 1; 
    // 反转左侧 0-k
    for(let i = 0; i < leftLen; i++) {
        [nums[i],nums[k-i-1]] = [nums[k-i-1],nums[i]];
    }
    // 反转右侧 k-len
    for(let i = 0; i < rightLen; i++) {
        [nums[i+k],nums[len-i-1]] = [nums[len-i-1],nums[i+k]];
    }
    return nums;
};

解四 [环状替换]

思路

例：nums = [1,2,3,4,5,6,7] k = 3

1. next = 3 => nums[3] = 4 start = 0; [4,2,3,1,5,6,7]
2. next = 6 => nums[6] = 7 start = 0; [7,2,3,1,5,6,4]
3. next = 2 => nums[2] = 3 start = 0; [3,2,7,1,5,6,4]
4. next = 5 => nums[5] = 6 start = 0; [6,2,7,1,5,3,4]
5. next = 1 => nums[1] = 2 start = 0; [2,6,7,1,5,3,4]
6. next = 4 => nums[4] = 2 start = 0; [5,6,7,1,2,3,4]

参考 leetcode官方题解

代码

var rotate = function(nums, k) {
    let len = nums.length,count = 0;
    k %= len;
    for(let start = 0; count < len; start++) {
        let current = start;
        do{
            let next = (current+k) % len;
            [nums[start], nums[next]] = [nums[next], nums[start]];
            current = next;
            count++;
        }while(start != current)
    }
    return nums;
};