1

初期配列：2 23 34 27 89 14 26 30 60

k = 3

インデックスi=1から開始して、配列内の要素26の後に（つまり、givenIndex = 6の後に）発生するようにk個の要素をシフトする必要があります。

最終的な配列： 2 89 14 26 23 34 27 30 60

余分なスペースを使用することは許可されていません。

私のアプローチ：

count = 0;   
while(count < k)  
{  
  count++;  
  temp = arr[i];  
  shift all elements from (i+1) to givenIndex to their immediate left position;  
  arr[givenIndex] = temp;  
}

最初の反復：
temp = 23
シフト後、すべての要素を[i + 1]（つまりindex = 2）からgivenIndex（つまりindex = 6）に1つずつ左
にシフトします2 34 27 89 14 26 26 30 60
。arr[givenIndex] =
この操作を適用した後の一時配列：2 34 27 89 14 26 23 30 60

同様
に、2回目の反復後の配列：2 27 89 14 26 23 34 30 60
3回目の反復後の配列：2 89 14 26 23 34 27 30 60

最悪の場合の複雑さO（n * k）ここで、nはnoです。配列内の要素の数。

O（n）で問題を解決できますか

4

3 に答える 3

1

この回転reverse()は、ヘルパー関数を使用して線形時間で実行できます。reverse(x, y)それがその場で逆転すると仮定しarray[x]..array[y]ます。

reverse(1, 3); // 27 34 23 .. .. ..
reverse(4, 6); // .. .. .. 26 14 89
reverse(1, 6); // 89 14 26 23 34 27

線形時間の記述reverseは簡単で、お気に入りの言語ライブラリで利用できる場合もあります（たとえば、C ++にはとが含まれますstd::rotate）std::reverse。

于 2012-08-07T07:25:09.353 に答える
0

私があなたのコード（そして例）からわかる限り、あなたはブロックの[i,i+k-1]後にブロックを配置しようとしていると思います[i+k,givenIndex]

その場合、@ Blastfurnaceの提案は、O（n）で1つのソリューションにつながり、余分なスペースはありません。

単に行う：

reverse(i,givenIndex)
reverse(i,givenIndex-k)
reverse(givenIndex-k+1,givenIndex)

そしてあなたはあなたが望むものを持っています:)

于 2012-08-07T07:39:49.190 に答える
0

質問は非常に素晴らしい
ですここであなたの要求された答えを見てください。JAVAを使用して配列リストをローテーションする方法を探している場合は、ここに完全なソリューションがあります。
public static void rotate(List list, int distance)

コレクション（ArrayListまたはLinkedList ...）をローテーションするだけです。
そのパラメーターはlist（あなたの場合arraylist）とdistance（あなたの場合k）です。類似点がわかりますか？これを使用するだけです。

于 2012-08-07T07:44:16.253 に答える