設計一個算法，把一個含有N個元素的數組循環右移K位，要求時間復雜度為O(N),且只允許使用兩個附件變量。比如abcd1234右移4位後為：1234abcd。 法一： 挨個遍歷，每個移動K位，復雜度 [cpp] 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; } } 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就可以了 [cpp] 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; } } 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 [cpp] 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); } 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); } [cpp] <PRE class=cpp name="code" sizcache="1" sizset="5"><PRE class=cpp name="code" sizcache="1" sizset="6"><PRE></PRE> <PRE></PRE> <PRE></PRE> <PRE></PRE> <PRE></PRE> <PRE></PRE> <PRE></PRE> <PRE></PRE> <PRE></PRE> <PRE></PRE> <PRE></PRE> <PRE></PRE> <PRE></PRE> <PRE></PRE> <PRE></PRE> <PRE></PRE> <PRE></PRE> <PRE></PRE> <PRE></PRE> <PRE></PRE> <PRE></PRE> <PRE></PRE> <PRE></PRE> </PRE></PRE>
