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);
}
}