単一の1D配列のみを使用して、n個の位置で配列の循環左シフトを行う効率的な方法。

Question

n個の整数の配列と数字dを指定すると、配列上で左回転を実行します。例array [1,2,3,4,5]とシフトは常に< =配列のサイズであり、1だけシフトするように要求されると出力は - > [2,3,4,5,1]になります。 arrayLeftRotationは（[]、INTをINT []

パブリックstatic int型：私は私のための時間複雑度はO（N^2）

コードであるとしてこれをさらに最適化することができ、正常に動作しているコードの下に書かれていますnは、int型のk）{O(n)時に、その場でこれを行うための巧妙なトリックがあります

if (n == 1 || n == k) 
     return a; 
    else { 
     int track = 0; 
     while (track < k) { 
      int start = a[0]; 
      for (int i = 0; i < n - 1; i++) { 
       a[i] = a[i + 1]; 
      } 
      a[n - 1] = start; 
      track++; 
     } 

     return a; 
    } 

} 

Answer 1

：

• は全体の配列を逆（つまり、インデックス間0（包括的）A nd n（排他的） `;
は
• はインデックス間の配列(n-k)（含む）とn（排他的）

（これは、その前提の部分を逆0（含む）と（排他的）(n-k)インデックス間の配列の一部を逆

0 <= k <= n;そうでない場合は、単にk >= 0場合、上記の、例えばk = k % nに係る等価回転をもたらす値にkの異なる値を見つける。）

それぞれO fの反転操作はO(n)であり、そのうち3つがあるので、全体的にはまだO(n)です。アレイをインバースすることも簡単です。余分なメモリオーバーヘッドはありません。