円弧の回転のこの線形複雑さの実装は正しいですか?アルゴリズム - 円形配列の回転
N =要素の数が K =回転
int write_to = 0;
int copy_current = 0;
int copy_final = a[0];
int rotation = k;
int position = 0;
for (int i = 0; i < n; i++) {
write_to = (position + rotation) % n;
copy_current = a[write_to];
a[write_to] = copy_final;
position = write_to;
copy_final = copy_current;
}
まあ、複雑さは確かに線形です。しかし、配列内の値を '#rotation 'の位置でずらして回転させることを期待するならば、これは伝統的に循環ローテーションと呼ばれていますが、これが最終的なものでないときには驚くでしょう。 –
http://stackoverflow.com/questions/11893053/circular-left-shift-of-an-array-by-n-positions-in-java – vadim
@vadim:その質問に対する受け入れられた答えは確かに正しいですが、よりきれいです1.最初のk要素を逆にする。 2.残りの要素を反転させます。 3.アレイ全体を逆にする。 (逆転はすべてインプレースです) – rici