単一の1D配列のみを使用して、配列をn桁左に循環させようとしています。2つの配列で実行できますが、1つを使用して実行する方法がわかりません。提案をお願いします
質問する
25376 次
15 に答える
24
実際には、そのための巧妙なアルゴリズムがあります。を使用Aして、配列Nを示し、配列のサイズnを示し、シフトする位置の数を示します。シフトの後、i-th要素をその((i + n) mod N)-th位置に移動させたいので、次のマッピングによって新しい位置を定義できます。
f(j) := (j + n) mod N (j = 0,...,N - 1)
このアルゴリズムの背後にある一般的な考え方は次のとおりです。要素を必要以上に移動したくないので、理想的には、最初の試行で各要素を適切な (シフトされた) 位置に配置するだけです。position の要素から始めるとしiます。やりたいことは、 position の要素を position に移動することですがi、f(i)その位置の要素を上書きするので、最初に position の要素を保存してからf(i)シフトを実行する必要があります。最初の要素をシフトしたら、シフトする別の要素を選択する必要があります。スペースを節約したいので、明らかな候補は先ほど保存した要素 ( position にあった要素f(i)) です。前と同じように、要素を位置に保存しますf(f(i))次に、保存した要素をその位置にコピーします。i, f(i), f(f(i)), f(f(f(i))), ...すでにシフトした要素に到達するまで、このプロセスを繰り返し続けます (positions を通過します) (有限の数の位置があるため、必ず移動することが保証されています)。すべての要素を通過した場合は完了です。そうでない場合は、別の要素 (まだシフトされていない) を選択し、位置jで、手順を繰り返します ( を通過しますj, f(j), f(f(j)), f(f(f(j))), ...)。それでおしまい。しかし、そのようなアルゴリズムを実装する前、またはこれが本当に良いアルゴリズムであるかどうかを判断する前に、いくつかの質問に答える必要があります。
position を繰り返し処理するとし
i, f(i), f(f(i)), ...ます。すでにシフトされた位置に到達したことをどのように確認できますか? 通過したすべての位置を保存する必要がありますか? もしそうなら、これはサイズ N の配列を保持する必要があることを意味し (すべての位置をカバーするために)、要素をシフトするたびにルックアップを実行する必要もあります。これにより、アルゴリズムが非常に非効率になります。幸いなことに、シーケンスi, f(i), f(f(i)), ...は position でラップする必要があるため、これは必要ありませんi。そのため、その位置に到達するまで待つだけで済みます。この主張は次のように証明できます。最初に遭遇する繰り返し要素が でないと仮定しますi。次に、シフトすると同じ位置に到達する2つの異なる要素が必要です-矛盾。を通過し
i, f(i), f(f(i)), ...たとしますが、シフトされていない要素がまだ残っています (シフトした要素の数を数えることでわかります)。jそのような要素を含む位置をどのように見つけるのでしょうか? また、この 2 回目の繰り返し ( を通過) が終了したら、シフトされていない要素でj, f(j), f(f(j)), ...3 番目の位置を見つけるにはどうすればよいでしょうか?kなどなど..これも、使用済みの使用\未使用の要素を考慮して配列を保存し、未使用の要素を見つける必要があるたびにルックアップを実行する必要があることを示唆している可能性があります。しかし、すぐに示すように、すべての開始位置(とiで表される) が隣接しているため、ここでもリラックスできます。つまり、位置 から開始すると、次に を選択し、次にjkii + 1i + 2など…</p>シーケンス
i, f(i), f(f(i)), ...とj, f(j), f(f(j)), ...(どこでiとjが異なるか) に共通の要素が含まれている可能性がありますか? これを行うと、同じ要素を 2 回シフトする可能性があり、間違った位置に配置される可能性があるため、アルゴリズムが役に立たないことを意味します。その場合の答えは (もちろん)、共通の要素を含めることはできないということです。そして、その理由を示します。
としましょうd := gcd(N, n)。整数のすべてについてi = 0,...,d - 1、次のセットを定義します。
S(i) := { kd + i | k = 0,...,N/d - 1}
S(0),...,S(d - 1)セットが一緒になってセットをカバーしていることは容易にわかります{0,...,N - 1}。また、セット内の要素を で割ると、余りが残り、S(i)別のセットの要素を で割ると、別の余り ( ) が残ることもわかります。したがって、2 つのセットに共通の要素が含まれることはありません。これにより、セットがのパーティションを形成することが確立されましたdiS(j)djS(0),...,S(d - 1){0,...,N - 1}
ここで、すべての について、集合を としてi = 0,...,d - 1定義します。の定義により、次のように記述できます。T(i)i, f(i), f(f(i)), ...fT(i)
T(i) = {(kn + i) mod N | k is an integer}
xが の要素である場合T(i)、一部の について次のように記述できることがわかりますk。
x = (kn + i) mod N = (k(n/d)d + i) mod N
を表すz := k(n/d) mod N/dと、 を掛けることで、次のようになりdます。
kn mod N = zd
それゆえ：
x = (kn + i) mod N = zd + i
したがって、xにもありS(i)ます。同様に、yからsome を取得S(i)すると、 some について次のことがわかりkます。
y = kd + i
そのようなもの(モジュラ逆数)gcd(n/d, N/d) = 1が存在するので、次のように書くことができます ( を掛ける):qq(n/d) mod N/d = 1kd
kd = kqn mod N
それゆえ：
y = kd + i = ((kq)n + i) mod N
したがって、yにもありT(i)ます。と結論付けT(i) = S(i)ます。この事実から、以前の主張を簡単に示すことができます。まず、セット{0,...,N - 1}は 3 番目のアサーション (共通の要素を含む 2 つのシーケンスはありません) のパーティションを形成するため、満たされます。次に、セットの定義により、隣接する要素S(i)の任意のグループを取得でき、それぞれが異なるセットに配置されます。これは、2 番目の主張を満たします。d{0,...N - 1}
これが意味することは、 position の要素を position の要素に、 positionの要素をpositionの0, d, 2d, ..., (N/d - 1)d要素に、というように置き換えるだけで、 position のすべての要素を回転させることができるということです。発生することが保証されています）。疑似コードの例を次に示します。n mod N02n mod Nn mod N0
temp <- A[0]
j <- N - (n mod N)
while j != 0 do
A[(j + n) mod N] <- A[j];
j <- (j - n) mod N
A[n mod N] <- temp;
これでセット全体がカバーされS(0)ます。残りのセット、つまり をカバーするS(1), … ,S(d-1)ために、最初のセットと同じ方法で各セットを単純に反復します。
for i <- 0 to d - 1
temp <- A[i]
j <- N - ((n - i) mod N)
while j != i do
A[(j + n) mod N] <- A[j];
j <- (j - n) mod N
A[(i + n) mod N] <- temp;
ネストされたループが 2 つありますが、各要素は 1 回だけ移動され、O(1)スペースが使用されることに注意してください。Java での実装例:
public static int gcd(int a, int b) {
while(b != 0) {
int c = a;
a = b;
b = c % a;
}
return a;
}
public static void shift_array(int[] A, int n) {
int N = A.length;
n %= N;
if(n < 0)
n = N + n;
int d = gcd(N, n);
for(int i = 0; i < d; i++) {
int temp = A[i];
for(int j = i - n + N; j != i; j = (j - n + N) % N)
A[(j + n) % N] = A[j];
A[i + n] = temp;
}
}
于 2013-08-09T20:19:46.993 に答える
2
一度に 1 要素ずつシフトし、単一の一時変数を使用して要素を保持し、要素をそれぞれに沿って 1 場所移動します。次に、シフトnを達成するためにこれを繰り返します。n
public static void main( String[] args ) {
int[] array = {1,2,3,4,5,6,7,8};
leftShift( array, 3);
System.out.println( Arrays.toString( array));
}
public static void leftShift(int[] array, int n) {
for (int shift = 0; shift < n; shift++) {
int first = array[0];
System.arraycopy( array, 1, array, 0, array.length - 1 );
array[array.length - 1] = first;
}
}
出力：
[4, 5, 6, 7, 8, 1, 2, 3]
System.arraycopy()高度に最適化されているため、非効率的ではありません。
于 2012-08-09T23:58:24.690 に答える
2
これは非常に簡単なアルゴリズムです。O(1) Space in O(n)
Algorithmを使用します。
- 配列を 0 から n (numberOfPositions) の位置に反転します
- 配列を n+1 から配列の長さ - 1 の位置に反転します
- 配列全体を 0 から長さ - 1 の位置に反転します
public class ArrayRotator {
private final int[] target;
private final int length;
public ArrayRotator(int[] seed) {
this.target = seed;
this.length = seed.length;
}
public void rotateInline(int numberOfPositions) {
reverse(0, numberOfPositions);
reverse(numberOfPositions + 1, length-1);
reverse(0, length-1);
}
private void reverse(int start, int end) {
for (int i = start; i <= (start + end)/2; i++) {
swap(i, start + end - i);
}
}
private void swap(int first, int second) {
int temp = this.target[second];
this.target[second] = this.target[first];
this.target[first] = temp;
}
}
たとえば、配列が is[1,2,3,4]およびnisであるとしましょうステップ 12
の
後、ステップ 2の
後、次のようになりますステップ 3の
後、次のようになります[2,1,3,4] [2,1,4,3] [3,4,1,2]
于 2016-01-29T11:12:47.170 に答える
1
もう1つの方法は、配列と仮想ゼロのインデックスを含む独自の構造をまとめることです。
于 2012-08-10T00:19:51.967 に答える
1
実際にはSystem.arraycopy、ある配列からすべてのデータを取得し、それを同じ長さの別の配列に入れるだけだと思います。
とにかく、その問題について考えるのは非常に興味深い作業です。私が今考えることができる唯一の解決策は、それを一つずつたわごとすることです. 別の配列を使用しないと、次のようになります。
for(int i = 0; i < shift;i++)
{
tmp = array[0];
for(int j = 0;j<array.length-1;j++)
array[j]=array[j+1];
array[array.length-1]=tmp;
}
30 項目を超える配列の場合は、これを使用する方が効率的ですが、次のようにします。
for (int i = 0; i < shift; i++) {
tmp = array[0];
System.arraycopy( array, 1, array, 0, array.length - 1 );
array[array.length - 1] = tmp;
}
しかし、配列サイズに近い大きな配列と大きなシフト、および短い配列と小さなシフトの場合、この方法が競争に勝ちます。
int[] array2 = new int[shift];
for (int i = 0; i < shift; i++)
{
array2[i] = array[i];
}
System.arraycopy(array, shift, array, 0, array.length - shift);
for (int i = array.length - shift; i < array.length; i++)
{
array[i] = array2[shift + i - array.length];
}
いくつかの配列サイズとシフトでテストしました。結果は次のとおりです
int[] array = new int[100000];
int shift = 99999;
ナノ秒単位: 1 番目の方法:5663109208 2 番目の方法:4047735536 3 番目の方法:6085690 したがって、実際には 3 番目の方法を使用する必要があります。それが役立つことを願っています
于 2012-08-10T01:30:03.563 に答える
1
反復とコピーによってデータをシフトできます。これは O(n) になります。別のアプローチはList、配列をラップし、循環シフトとして公開する実装を作成することです。getこれには、または反復が実行されるときに実際のシフトが遅延して行われるという利点がありました。
于 2012-08-09T23:12:18.040 に答える
0
この github リンクをチェックしてください:
円形ShiftToLeftInPlace
于 2014-01-16T23:54:11.003 に答える
0
for (int i = 0; i < n; i++)
array[array.length - n + i] = array[i];
for (int i = 0; i < array.length - n; i++)
array[i] = array[i + n];
于 2012-08-09T23:49:34.320 に答える
-1
これはどう？
// Left shift the array in O(n) with O(1) space.
public static void leftShift(int[] array, int n) {
int temp;
int len = array.length;
for (int i = 0; i < n; i++) {
temp = array[len - n + i];
array[len - n + i] = array[i];
array[i] = array[n + i];
array[n + i] = temp;
}
}
于 2014-11-29T06:53:15.470 に答える