旋转数组

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
示例 1:
输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]

方法一

// 性能较差劲
//void rotate(int* nums, int numsSize, int k) {
//    int tem = 0;
//    for (int i = 1; i <= k; i++) {
//        tem = nums[numsSize - 1];
//        for (int j = numsSize - 1; j >= 0; j--) {
//            nums[j] = nums[j - 1];
//        }
//        nums[0] = tem;
//    }
//}

方法二

// 执行用时 4ms 高效算法
void reverse(int *arr, int start, int end) {
    int temp = 0;
    while (start < end) {
        temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
        start++;
        end--;
    }
}

void rotate(int* nums, int numsSize, int k) {
    if (nums == NULL || numsSize == 0 || k % numsSize == 0) {
        return;
    }
    int kcount = k % numsSize;
    int middle = numsSize - kcount;
    reverse(nums, 0, middle - 1); // reverse left part
    reverse(nums, middle, numsSize - 1); // reverse right part
    reverse(nums, 0, numsSize - 1); // reverse whole part
}
int main(int argc, const char * argv[]) {
    @autoreleasepool {
     
        int arr[] = {1,2,3,4,5,6,7};
        rotate(arr, 7, 3);
        for (int i = 0; i < 7; i++) {
            printf("%d ",arr[i]);
        }
        printf("\n");
    }
    return 0;
}

这里有一个很巧妙的方法：

利用数组的length - k 把数组 分为两半；

reverse 左边和右边的数组；

reverse 总数组。

举一个例子：

1 2 3 4 5 6 7　　如果k = 3 的话， 会变成 5 6 7 1 2 3 4

1 2 3 4 5 6 7　　middle = 7 - 3 = 4，分为左边 4个数字，右边 3个数字

4 3 2 1 7 6 5　　分别把左右reverse 一下

5 6 7 1 2 3 4　　把总数组reverse 一下就会得到答案

参考文章：
http://www.cnblogs.com/grandyang/p/4298711.html
http://www.cnblogs.com/grandyang/p/4298711.html