###### tags: `Leetcode` `medium` `array` `pointer` `swap` `python` `c++`

# 189. Rotate Array

## [題目連結]:https://leetcode.com/problems/rotate-array/description/

## 題目:
Given an array, rotate the array to the right by k steps, where k is non-negative.

**Follow up:**
* Try to come up with as many solutions as you can. There are at least three different ways to solve this problem.
* Could you do it in-place with O(1) extra space?

**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]

## 解題想法:
* 題目為將尾移到頭算一次rotate: rotate K次
* 要求O(1) extra space
* 題目要求空間 O(1)
* 通常就表示這個題目高機率可以用
* pointer or swap 的方式解出來 (想辦法只用交換的)

想法: 
nums = [1,2,3,4,5,6,7], k = 3
n=len(nums)=7
k%n=3
Step1: 反轉nums
    nums = [7,6,5,4,3,2,1]
Step2: 反轉前半段nums[:k] pos 0~2
    nums = [5,6,7,4,3,2,1]
Step3: 反轉後半段nums[K:] pos 3~
    nums = [5,6,7,1,2,3,4] 
end~

## Python:

class Solution(object):
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        #space O(1)
        n=len(nums)
        if n==0:
            return
        k%=n
        self.reverse(nums,0,n-1) #先將整個nums反轉
        self.reverse(nums,0,k-1) #將前半段nums反轉
        self.reverse(nums,k,n-1) #將後半段nums反轉
        
    def reverse(self,nums,start,end):
        while start<end:
            nums[start],nums[end]=nums[end],nums[start]
            start+=1
            end-=1

nums = [1,2,3,4,5,6,7]
print("Original     :",nums)
k = 3
result = Solution()
ans = result.rotate(nums,k)
print("After rotated:",nums)

#Original     : [1, 2, 3, 4, 5, 6, 7]
#After rotated: [5, 6, 7, 1, 2, 3, 4]

## C++:

#include<bits/stdc++.h>
using namespace std;

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

int main(){
    Solution res;
    vector<int> nums={1,2,3,4,5,6,7};
    int k=3;
    res.rotate(nums,k);
    for (auto val:nums){
        cout<<val<<" ";
    }
    cout<<endl;
    //5 6 7 1 2 3 4
    return 0;
}