Leetcode 89. Rotate Array

Rotate Array : 給定一個數組，將數組向右旋轉 k 步，其中 k 是非負數

Python

方法一 :

1. 先用 tmp 紀錄最後一段的數組切片(比方說上面那個例題，先用tmp紀錄[5, 6, 7])
2. 將nums的第k項到最後一項用0到n-k項取代([4, 5, 6, 7]被[1, 2, 3, 4]取代)
3. 最後再將tmp放回去 ([1, 2, 3]被[5, 6, 7]取代)。

class Solution:
    def rotate(self, nums, k: int) -> None:
        n = len(nums)
        # k 取餘數，比方說等於n根本不用旋轉
        k %= n
        if k != 0:
            # 1
            tmp = nums[-k:]
            # 2
            nums[k:n] = nums[:n - k]
            # 3
            nums[0:k] = tmp

方法二 :

1. 首先先將整個數組翻轉一次
2. 接下來看k多少決定左邊以及右邊的分界
3. 翻轉左邊，然後翻轉右邊

class Solution:
        def rotate(self, nums, k: int) -> None:
            k %= len(nums)
            
            def reverse(nums, i, j):
                while i < j:
                    nums[i], nums[j] = nums[j], nums[i]
                    i += 1
                    j -= 1
            
            reverse(nums, 0, len(nums)-1)
            reverse(nums, 0, k-1)
            reverse(nums, k, len(nums)-1)  

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() - k); // 翻轉前n-k個元素
        reverse(nums.end() - k, nums.end()); // 翻轉後k個元素
        reverse(nums.begin(), nums.end()); // 翻轉整個數組
    }
};

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k = k % n; //  如果k大於n，取餘數，可以避免不必要的旋轉。
        if (k == 0) return; // 特例，如果k為0，直接返回原數組。
        int left = 0, right = n - 1;
        while (left < right) { // 先翻轉整個數組
            swap(nums[left], nums[right]);
            left++;
            right--;
        }
        left = 0;
        right = k - 1;
        while (left < right) { // 再翻轉前k個元素
            swap(nums[left], nums[right]);
            left++;
            right--;
        }
        left = k;
        right = n - 1;
        while (left < right) { // 最後翻轉剩下的元素
            swap(nums[left], nums[right]);
            left++;
            right--;
        }
    }
};