數組循環移位的幾種解法

題目描寫叙述：

設計一個算法,把一個含有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.

解法三：

這裡有一個非常巧妙的方法來實作數組循環。

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
}