[LeetCode] 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.

解题思路1

首先把数组复制一遍，然后找到元素之间的映射关系： newnum[i] = oldnum[(i - k + n) % n]，时间复杂度为O(n)，空间复杂度为O(n)。

实现代码1

/*****************************************************************
    *  @Author   : 楚兴
    *  @Date     : 2015/2/24 16:58
    *  @Status   : Accepted
    *  @Runtime  : 33 ms
******************************************************************/
class Solution {
public:
    void rotate(int nums[], int n, int k) {
        int *temp = new int[n];
        memcpy(temp, nums, n * sizeof(int));

        k = k % n;
        for (int i = 0; i < n; i++)
        {
            nums[i] = temp[(i - k + n) % n];
        }

        delete [] temp;
    }
};

解题思路2

将数组看成是一个环，每个元素每次往前走一步，循环k次。时间复杂度为O(k*n)，耗时较长，空间复杂度为O(1)。

实现代码2

/*****************************************************************
    *  @Author   : 楚兴
    *  @Date     : 2015/2/24 17:10
    *  @Status   : Accepted
    *  @Runtime  : 872 ms
******************************************************************/
class Solution {
public:
    void rotate(int nums[], int n, int k) {
        k = k % n;
        while (k--)
        {
            int temp = nums[n - 1];
            for (int i = n - 1; i > 0; i--)
            {
                nums[i] = nums[i - 1];
            }
            nums[0] = temp;
        }
    }
};

解题思路3

①将整个数组反转
②将由分割点分割的两个数组分别反转
即：1 2 3 4 5 6 7 -> 7 6 5 | 4 3 2 1 -> 5 6 7 | 1 2 3 4
时间复杂度为O(n)，空间复杂度为O(1)。

实现代码3

/*****************************************************************
    *  @Author   : 楚兴
    *  @Date     : 2015/2/24 17:39
    *  @Status   : Accepted
    *  @Runtime  : 25 ms
******************************************************************/
class Solution {
public:
    void rotate(int nums[], int n, int k) {
        k = k % n;
        rev(nums, 0, n - 1);
        rev(nums, 0, k - 1);
        rev(nums, k, n - 1);
    }

    void rev(int num[], int left, int right)
    {
        int temp;
        while (left < right)
        {
            temp = num[left];
            num[left++] = num[right];
            num[right--] = temp;
        }
    }
};