189. Rotate Array

Leetcode

https://leetcode.com/problems/rotate-array/description/

題目

Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.

Example 1:

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

Example 2:

Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation: 
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]

解答

• 方法 1

每一步驟都把最後一個元素拿出來放到最前面的元素，這樣做法會正確但結果是 TLE

var rotate = function (nums, k) {
    const step = k % nums.length;

    for (let i=0; i<step; i++) {
        const end = nums.pop();
        nums.unshift(end);
    }
};

Time Limit Exceeded

• 方法 2

分成兩部分來處理：

1. 矩陣後半段超過範圍的元素用另一個 矩陣(temp) 記錄下來，之後移回前半段

2. 矩陣前半段沒有超過範圍的元素，直接移到後半段去

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

旋轉後的結果會是 [3, 4, 5, 6, 7, 1, 2]

其中 [3, 4, 5, 6, 7] 是超過範圍的 temp 矩陣，[1, 2] 是前半段移到後半段的元素

var rotate = function (nums, k) {
    const step = k % nums.length; // 取餘數

    const temp = [];
    // 從第一個要放到 前半段的元素(3) 開始取
    for (let i = nums.length - step; i < nums.length; i++) {
        temp.push(nums[i]);
    }

    // 由後往前
    for (let i = nums.length - 1; i >= 0; i--) {
        if (i >= step) {
            // 先將前半段元素移到後半段
            nums[i] = nums[i - step];
        } else {
            // 前半段元素用 temp 替代
            nums[i] = temp[i];
        }
    }
};

Runtime: 91 ms Beats 21.02% of users with JavaScript

Memory: 59.50 MB Beats 27.29% of users with JavaScript

參考資料

https://skyyen999.gitbooks.io/-leetcode-with-javascript/content/questions/189md.htmlskyyen999.gitbooks.io

• 方法 3 - 逆向排序

這個方法可以說是要看過才會了

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

旋轉後的結果會是 [3, 4, 5, 6, 7, 1, 2]，而這結果可以分成三個步驟完成

1. 整體先進行一次逆向排序：[7, 6, 5, 4, 3, 2, 1]

2. 對於前面 k 個元素進行逆向排序 [7, 6, 5, 4, 3] => [3, 4, 5, 6, 7]

3. 對 k 後面的元素也進行逆向排序 [2, 1] => [1, 2]

最後得到的就是我們要的答案了

var rotate = function (nums, k) {
    const step = k % nums.length;

    const reverse = (start, end) => {
        while(start < end) {
            const temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }

    reverse(0, nums.length - 1);
    reverse(0, step - 1);
    reverse(step, nums.length - 1);
};

Runtime: 72 ms Beats 88.99% of users with JavaScript

Memory: 56.16 MB Beats 71.71% of users with JavaScript

參考資料

189. Rotate Array · leetcodeleetcode.wang