设计一个算法,把一个含有N个元素的数组循环右移K位,要求时间复杂度为O(N),且只允许使用两个附件变量。比如abcd1234右移4位后为:1234abcd。
法一:
挨个遍历,每个移动K位,复杂度
- RightShift(int* arr,int N, int K)
- {
- while(K--)
- {
- int t=arr[N-1];
- for(int i=N-1;i>0;i--)
- arr[i]=arr[i-1];
- arr[0]=t;
- }
- }
法二:可以进一步优化,因为K远大于N时,存在重复移动,即移动存在周期性,周期就是N,所以移动K%=N就可以了
- RightShift(int* arr,int N, int K)
- {
- K%=N;
- while(K--)
- {
- int t=arr[N-1];
- for(int i=N-1;i>0;i--)
- arr[i]=arr[i-1];
- arr[0]=t;
- }
- }
法三:分组逆序排序,具体过程分三步,以abcd1234移动4位为例子
逆序排列abcd:abcd1234 => dcba1234
逆序排列1234:dcba1234 => dcba4321
逆序排列dcba4321: dcba4321 => 1234abcd
- Reverse(int* arr, int b, int e)
- {
- for(;b<e;b++,e--)
- {
- int tmp=arr[e];
- arr[e]=arr[b];
- arr[b]=tmp;
- }
- }
- RightShift(int* arr,int N, int K)
- {
- K%=N;
- Reverse(arr,0, N-K-1);
- Reverse(arr, N-K,N-1);
- Reverse(arr, 0, N-1);
- }