[LeetCode] 189. Rotate Array (JS)

5 個月前

內容目錄 隱藏

題目

給定一個整數陣列 nums ，將陣列向右旋轉 k 步，其中 k 為非負數。

解法

最開始想的是，直接 pop 再 unshift 回去不就好了？

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var rotate = function(nums, k) {
    // steps = 所需旋轉的次數
    // 因為旋轉次數可能大於 nums 長度，所以用取模(%)計算
    const steps = k % nums.length
    for (let i = 0; i < steps; i++) {
        const lastNum = nums.pop()
        nums.unshift(lastNum)
    }
};

雖然結果是對的，但會超時(Time Limit Exceeded)。題目最後有提到，希望可以只花費O(1)的額外空間並且in-place的解決這道題。

稍微調整一下上方的程式碼，把一個一個遍歷改成直接整段搬過來到陣列最前方就可以實現：

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var rotate = function(nums, k) {
    // steps = 所需旋轉的次數
    // 因為旋轉次數可能大於 nums 長度，所以用取模(%)計算
    const steps = k % nums.length
    const subNums = nums.splice(-steps)
    nums.unshift(...subNums)
};

補充

比較要注意的是 unshift() 的用法，不能寫 nums.unshift([...subNums]) 而是要寫 nums.unshift(...subNums)

var arr = [1, 2];

arr.unshift(0);
// arr is [0, 1, 2]

arr.unshift(-2, -1); // = 5
// arr is [-2, -1, 0, 1, 2]

arr.unshift([-3]);
// arr is [[-3], -2, -1, 0, 1, 2]

而 Array.prototype.copyWithin() 是將陣列一部分淺拷貝到另一位置覆蓋，和題目需求不一致所以不能使用。