189. Rotate Array

[fockspaces]

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]

[fockspaces]

解法一：以 end - k 為軸，左右先翻轉，再整體翻轉一次 因為旋轉 k 次（k < n），表示每個元素都前進了 k 步

假設 k = 3 以左邊為例，4 在第一次翻轉時往後走了 3 步，第二次翻轉往前走了 6 步，總共往前走 6 - 3 步 每個元素都可以用這個規律往前走 3 步

// 1,2,3,4,| 5,6,7 // 4 3 2 1 | 7 6 5 // 5 6 7 1 2 3 4

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        k %= nums.size();
        if(k == 0) return;
        reverse(nums.begin(), nums.end() - k);
        reverse(nums.end() - k, nums.end());
        reverse(nums.begin(), nums.end());
    }
};

[fockspaces]

解法二：認真走一遍 用一個數組 prev 存原本的值 之後 iterate 數組，把目標放進對應位置回 nums

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        vector<int> prev = nums;
        for(int i = 0; i < nums.size(); i++) 
            nums[(i + k) % nums.size()] = prev[i];
    }
};

[fockspaces]

先 copy 取出選定範圍的 array 後再倒轉會更好 例如 [start : end][::-1]

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        k = k % n
        nums[:n-k]=nums[:n-k][::-1]
        nums[n-k:]=nums[n-k:][::-1]
        nums[:] = nums[::-1]