旋轉(zhuǎn)數(shù)組

給定一個數(shù)組，將數(shù)組中的元素向右移動 k 個位置，其中 k 是非負數(shù)。
示例 1:
輸入: [1,2,3,4,5,6,7] 和 k = 3
輸出: [5,6,7,1,2,3,4]
解釋:
向右旋轉(zhuǎn) 1 步: [7,1,2,3,4,5,6]
向右旋轉(zhuǎn) 2 步: [6,7,1,2,3,4,5]
向右旋轉(zhuǎn) 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;
//    }
//}

方法二

// 執(zhí)行用時 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;
}

這里有一個很巧妙的方法：

利用數(shù)組的length - k 把數(shù)組 分為兩半；

reverse 左邊和右邊的數(shù)組；

reverse 總數(shù)組。

舉一個例子：

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個數(shù)字，右邊 3個數(shù)字

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

5 6 7 1 2 3 4　　把總數(shù)組reverse 一下就會得到答案

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