leetcode | Medium | 189. Rotate Array

題目: https://leetcode.com/problems/rotate-array/

問題描述

給定長度為 n 的陣列 nums，將陣列中的元素向右旋轉 k 個位置，其中 k 是非負數。

輸入: nums = [1,2,3,4,5,6,7], k = 3
輸出: [5,6,7,1,2,3,4]
解釋:
向右旋轉 1 步: [7,1,2,3,4,5,6]
向右旋轉 2 步: [6,7,1,2,3,4,5]
向右旋轉 3 步: [5,6,7,1,2,3,4]

解法一：使用額外陣列的直觀解法

直觀的想法是使用一個額外的陣列，將旋轉後的位置預先計算好，然後將元素放在正確的位置。

時間複雜度：O(n)

因為需要遍歷整個陣列一次。

C++程式碼：

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> temp(n); // 建立臨時陣列
        k = k % n; // 處理 k 大於 n 的情況
        for(int i = 0; i < n; i++) {
            temp[(i + k) % n] = nums[i]; // 計算新位置並賦值
        }
        nums = move(temp); // 將結果移回原陣列
    }
};

解釋：

• 創建一個與原陣列大小相同的臨時陣列 temp。
• 遍歷原陣列，計算每個元素在旋轉後的位置 (i + k) % n，並將元素放入 temp 中的對應位置。
• 將 temp 中的元素移回原陣列 nums。

解法二：反轉

為了減少空間複雜度，我們可以考慮在原陣列上進行操作，不使用額外的空間。核心思想是通過反轉陣列來達到旋轉的效果。

時間複雜度：O(n)

反轉操作需要遍歷陣列，但總共只遍歷了 3 次。

C++程式碼：

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k = k % n; // 處理 k 大於 n 的情況
        reverse(nums.begin(), nums.end()); // 整體反轉
        reverse(nums.begin(), nums.begin() + k); // 反轉前 k 個元素
        reverse(nums.begin() + k, nums.end()); // 反轉後 n - k 個元素
    }
};

解釋：

• 整體反轉陣列： 將陣列的所有元素反轉，這樣原本的順序被顛倒。
• 反轉前 k 個元素： 將陣列的前 k 個元素再次反轉，使其回到正確的順序。
• 反轉後 n - k 個元素： 將剩下的元素（從第 k 個位置到結尾）反轉，恢復正確順序。

步驟拆分：

以陣列 [1,2,3,4,5,6,7] 和 k = 3 為例：

1. 整體反轉：

   複製程式碼原陣列：1 2 3 4 5 6 7
   
   反轉後：7 6 5 4 3 2 1

2. 反轉前 k 個元素（前 3 個）：

   複製程式碼部分反轉：5 6 7 | 4 3 2 1

3. 反轉後 n - k 個元素（後 4 個）：

   複製程式碼最終結果：5 6 7 1 2 3 4

以上是 Hua 在 LeetCode 的解題分享，有想法或是建議歡迎在底下討論。

Day Day Good, Day Day Up !