数组循环移位的几种解法

「爱情、让人受尽委屈。」 2022-04-10 11:54 149阅读 0赞

题目描写叙述：  
设计一个算法,把一个含有N个元素的数组循环右移K位。

**解法一:**  
最easy想到的就是每次将数组中的元素右移一位，循环K次。

#include<iostream>
    using namespace std;
    void 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;
        }
    
     }
    
    int main(){
       int num[4] = {
          1,3,7,9};
       for(int i = 0; i < 4;i++){
          cout<<num[i]<<' ';
       }
       cout<<'\n';
       RightShift(num,4,2);
       for(int i = 0; i < 4;i++){
          cout<<num[i]<<' ';
       }

这里的复杂度为K\*N次，我们接下来再用一个方法来改进。

**解法二：**  
用空间来换时间，申请一个大小为K%N的数组，由于循环移位K次，假设K > N。则其效果与移动K%N次是一样的。

所以在解法一，我们能够加上 K = K %N 这句。  
假如原数组： 1 2 3 4 5 6 7 须要右移4次。那么我们想要的结果是： 5 6 7 1 2 3 4  
我们注意到。事实上就是将1234前四个元素拿出来（变成array A: \_ \_ \_ \_ 5 6 7, array B:1 2 3 4），然后将567前移充填(A 变成 5 6 7 \_ \_ \_ \_)。然后我们仅仅要将 B 数组再加入到A 数组后面就完毕了。 最后 (A : 5 6 7 1 2 3 4)

void RightShift(int *arr, int N, int K){
         K = K % N;
         int *sp = (int*)malloc(K*sizeof(int));
         int i = 0,s = 0;
         for(; i < K;i++){        // 将数组前K 位存入sp中
             sp[i] = arr[i];
         }
         for(;i<N;i++,s++){       // 将数组第K+1 - N 位移到arr前端。
            arr[s] = arr[i];
         }
         for(i = 0; s < N;i++,s++){    // 将sp中的数取出，拼入arr数组。
            arr[s] = sp[i];
         }
    }

这里对数组进行了复制K次。将后面的元素前移N-K次，然后再将K 个元素拼接到数组后面进行了K次操作。一共进行了N+K次操作。然而空间复杂度为K.

**解法三：**  
这里有一个非常巧妙的方法来实现数组循环。

假如原数组： 1 2 3 4 5 6 7 须要右移4次，那么我们想要的结果是： 5 6 7 1 2 3 4。  
1.将1234逆置 变成 4321  
2.将567逆置 变成 765  
3.将两个逆置数组拼接： 4321765  
4.将这个已拼接的数组逆置： 5671234 就成了我们想要的结果了。

void Reverse(int *arr,int start,int end){      //逆置
        for(; start < end;start++,end--){
               int s = arr[end];
               arr[end] = arr[start];
               arr[start] = s;
          }
    }
    
    void RightShift(int* arr,int N, int K){
          K = K%N;                       //相应上文步骤
          Reverse(arr,0,K-1);           //1 
          Reverse(arr,K,N-1);           //2
          Reverse(arr,0,N-1);           //4
    }

上述算法Reverse函数时间复杂度分别为K/2, (N-K)/2,N/2, 所以总的复杂度为O（N）。空间复杂度为O（1）