[LeetCode]189.Rotate Array

[LeetCode]189.Rotate Array

題目

Rotate an array of n elements to the right by k steps.

For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

Note:
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.

Hint:
Could you do it in-place with O(1) extra space?

思路一

跟字符串左右旋轉操作一樣的思路。
三次翻轉法，第一次翻轉前n-k個，第二次翻轉後k個，第三次翻轉全部。

代碼一

    /*--------------------------------------------
    *   日期：2014-02-25
    *   作者：SJF0115
    *   題目: 189.Rotate Array
    *   網址：https://oj.leetcode.com/problems/rotate-array/
    *   結果：AC
    *   來源：LeetCode
    *   博客：
    ------------------------------------------------*/
    #include 
    #include 
    using namespace std;

    class Solution {
    public:
        void rotate(int nums[], int n, int k) {
            if(n <= 1){
                return;
            }//if
            k = k % n;
            if(k <= 0){
                return;
            }//if
            // 翻轉前n-k個
            Reverse(nums,0,n - k - 1);
            // 翻轉後k個
            Reverse(nums,n - k,n - 1);
            // 翻轉全部
            Reverse(nums,0,n - 1);
        }
    private:
        void Reverse(int nums[],int left,int right){
            int tmp;
            for(int i = left,j = right;i < j;++i,--j){
                // 交換
                swap(nums[i],nums[j]);
            }//for
        }
    };
    int main() {
        Solution solution;
        int A[] = {1,2,3,4,5,6,7};
        int n = 7;
        int k = 2;
        solution.rotate(A,n,k);
        for(int i = 0;i < n;++i){
            cout<