问题:把一个N个元素的数组循环右移K位,要求时间复杂度为O(N)。
解析:如abcd1234右移4位 要变成1234abcd
1,逆序排列abcd->dcba1234
2,逆序排列1234->dcba4321
3,逆序排列dcba4321
代码如下:
void Reverse(int * arr, int beg, int end) {for (; beg < end ; beg++, end—){int temp = arr[beg];arr[beg] = arr[end];arr[end] = temp;} } void RightSift(int* arr, int N, int K) {K = K%N;//这里一定要注意,K不一定是小于N的,如果K大于N呢?呵呵Reverse(arr, 0, N – K -1);Reverse(arr, N – K , N -1);Reverse(arr, 0, N - 1); }