# 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.

&#x20;

**Example 1:**

<pre><code><strong>Input: nums = [1,2,3,4,5,6,7], k = 3
</strong><strong>Output: [5,6,7,1,2,3,4]
</strong><strong>Explanation:
</strong>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]
</code></pre>

**Example 2:**

<pre><code><strong>Input: nums = [-1,-100,3,99], k = 2
</strong><strong>Output: [3,99,-1,-100]
</strong><strong>Explanation: 
</strong>rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]
</code></pre>

### 解答 <a href="#ti-jie" id="ti-jie"></a>

* **方法 1**

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

```javascript
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]` 是前半段移到後半段的元素

```javascript
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

**參考資料**

{% embed url="<https://skyyen999.gitbooks.io/-leetcode-with-javascript/content/questions/189md.html>" %}

* **方法 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]`

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

```javascript
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

**參考資料**

{% embed url="<https://leetcode.wang/leetcode-189-Rotate-Array.html#%E8%A7%A3%E6%B3%95%E5%9B%9B>" %}
