LeetCode 189. Rotate Array

題目

Rotate an array of n elements to the right by k steps.

For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

Note: Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.

翻譯

給一個n值,n代表陣列中包含1~n個元素與一個整數k,將陣列裡面的元素向右旋轉k次。

範例:

n=7,k=3, array[1,2,3,4,5,6,7] -->  [5,6,7,1,2,3,4]

思路

如果一個陣列的長度為n,向右旋轉k次,其實就跟沒旋轉一樣,所以實際上要旋轉的次數step = n%k。

向右旋轉1次,就是將陣列最後面的元素搬到最前面,使用javascript array的pop()可以取出最後一個元素, unshift(x)可以將元素插到陣列的最前面,這解法太簡單了,因此我們這邊不用這兩個方法來解題。

這邊我們用一個暫存陣列temp儲存向右旋轉的元素,需要旋轉k次temp裡面就有幾個元素。題目要求只能在一開始的nums陣列內操作 ,所以接下來就是把nums內沒被旋轉的元素搬到nums的後面,接著將temp放到nums前面。

解題

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var rotate = function(nums, k) {
    // ex. [1,2,3] k=5  與 [1,2,3] k=2 相同  
    var step = k%nums.length;
    var temp = [];

    // 將向右旋轉的元素裝到temp, [1,2,3] k=2, temp = [2,3] 
    for(var i = step - 1 ; i >= 0 ; i--) {
        var index = nums.length-1-i;
        temp.push(nums[index]);
    }

    for(var j = nums.length - 1; j >= 0 ; j--){
        if( j >= step){
            // 將nums內沒被旋轉的元素往後移k格,[1,2,3] -> [x,x,1] 
            nums[j] = nums[j-step];
        } else {
            // 將temp放到nums的前面 [2,3,1]
            nums[j] = temp[j];
        }
    }

};

用javascript強大的array method解題

var rotate = function(nums, k) {
    var step = k%nums.length;
    for(var i = 0 ; i < step ; i++){
        var value = nums.pop();
        nums.unshift(value);
    }
}

results matching ""

    No results matching ""