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) 的原地算法。

解法1：最直覺的，我們直接看k有多少，然後直接向右移動k次，最後一位則移到開頭位置。

這邊有一個問題要注意，當for迴圈內給定” var” i = 0時，變數i是var命令宣告的，在全域性範圍內都有效，所以全域性只有一個變數i，而在沒有”var”宣告的時候，每次迴圈內的i都將會是一個獨立變數，會導致這組程式超過leetcode執行時間。

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var rotate = function(nums, k) {
    const n = nums.length;
    if (n <= 1) {
        return;
    }
    var k = k % n; // 減少k 的橫移次數
    var targetCache = 0;
    var currentCache = 0;
    for (var i = 0; i < k; i++) { // 計算橫移幾次
        for (var j = 0; j < n; j++) { // 計算nums從0開始
            if (j == n - 1) { // 當遍歷到最後一位時
                nums[0] = currentCache; // 把第一位設為當前的數字
                break;
            }
            if (j == 0) { // 如果剛開始遍歷
                currentCache = nums[j]; // 把當前數字存起來
            }
            targetCache = nums[j + 1]; // 將下一位數存起來
            nums[j + 1] = currentCache; // 將下一位數設為目前的數字
            currentCache = targetCache; // 將目標數字存起來供下次使用
        }
    }
};

解法2：每次把最後一個元素移到第一位，後面的元素後移一位，循環往復，直到第k次。

上面寫法還是太繞太費時了，參考網路上解法，改寫了一下

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var rotate = function(nums, k) {
    var n = k % nums.length;
    for (i = 0; i < n; i++) {
        nums.unshift(nums.pop());
    }
};

題目連結：https://leetcode-cn.com/problems/rotate-array/description/

Copyright secured by Digiprove © 2018