0

特定の条件を満たす要素が配列の最後に残るように、2D 配列内のすべての要素を上下にシフトする方法を探しています。私が意味することの簡単な例：

1 と 4 つのゼロで埋められた 2D 整数配列。

1 1 1 1 1  
1 1 1 1 0  
1 1 1 0 1  
1 1 1 1 1  
0 0 1 1 1

私がやりたいことは、他の要素をシフトして穴 (ゼロ) を埋め、最後にゼロを残すことです。望ましい結果は次のとおりです。

1 1 1 1 1  
1 1 1 1 1  
1 1 1 1 1  
1 1 1 1 1  
1 0 0 0 0

私のプロジェクトでは、オブジェクトの 2D 配列を扱っています。その状態がシフトを決定する要因です。この結果を達成する基本的なアルゴリズムを探しています。これを行う簡単な方法はありますか？

4

7 に答える 7

2

配列を反復処理し、ゼロを数えます。ゼロを見つけるたびに、カウンターに 1 を追加し、ゼロを 1 に置き換えます。次に、配列の末尾から先頭に移動し、N の位置を 0 に置き換えます。ここで、N はゼロの総数です。

于 2013-04-09T11:11:00.380 に答える
0

上記の正確な質問の場合、解決策は次のようになります。

配列の左上隅と右下にある 2 つのポインターから始めます。これらの最初と 2 番目のポインターをそれぞれ呼び出します。最初のポインター行を使用して配列を反復処理します。最後に配置する要素 (この場合は「0」) を見つけたら、2 番目の要素が指す要素を確認します。2 番目の要素が 0 の場合、2 次元配列の最後の 2 番目の要素を指すように 2 番目のポインタをデクリメントします。これも '0' である場合は、この要素をチェックし、2 番目のポインターを再度デクリメントし、'1' (配列の先頭にある必要がある要素) に到達するまで繰り返します。次に、2 つの要素を交換します。ポインタが互いに交差している場合はいつでも、配列は要件に従ってソートされています。

次の Java コードはこれを行います。最初は、変数 endi と endj が最後の要素 (2 番目のポインター) を指し、変数 i と j が最初の要素 (最初のポインター) を指します。配列のサイズは m X n です。

for(i=0;i<m;i++)
    {
        for(j=0;j<n;j++)
        {
            if(a[i][j]==0)
            { 
                while(a[endi][endj]!=1 && i*m+j<endi*m+endj) //second part of the condition checks if i,j and endi,endj haven't crossed over
                {
                    endj--;
                    if(endj==-1)
                    {
                        endj=n-1;
                        endi--;
                        if(endi==-1)
                        {
                            disparr(a,m,n);
                            System.exit(0);
                        }
                    }
                }
                if(!(i*m+j<endi*m+endj))//if the pointer have crossed over
                {
                    disparr(a,m,n);
                    System.exit(0);
                }    
                int t=a[i][j];
                a[i][j]=a[endi][endj];
                a[endi][endj]=t;

            }
        }
    }

上記のコードに対する他の改善が可能かもしれません。たとえば、関数へのポインターをデクリメントして呼び出すためのコードを削除するなどです。しかし、コードは問題なく動作します。

于 2013-04-09T12:28:52.040 に答える
0

最初の配列のすべての配列に対してバブルソートを実行し、順序で並べ替えます

for (i=0; i<array1.length; i++){
   yourBubblesort(array1[i]);
}

バブルソートの実装はとても簡単です。宿題で何かをしなければなりません

于 2013-04-09T11:10:36.077 に答える
0

この方法を試してください

public void shiftZeros(int[] arr )
{
int count;
for(int j=0;j<arr.length-1;j++)
{
  if(arr[j]=0)
   {
    arr[j]=1;
    count++;
   }
}

for(int j=arr.length-1,i=1;i<count;i++,j--)
{
   arr[j]=0;
}

}
于 2013-04-09T11:18:38.553 に答える
0

列を降順に並べ替えてから、各行を降順に並べ替えてみませんか? これを行うために存在するアルゴリズムはたくさんあります。

于 2013-04-09T11:42:43.977 に答える
0

これは、新しい配列へのコピーを使用した1つのアプローチです

  • シフトされた要素/最終結果を保持するための新しい配列を作成します
  • 配列を反復処理する
  • 新しい配列の最後の空いている場所に移動する (条件を満たす) 要素をコピーします。
  • 配列内の次の空いている場所に移動しない (条件を満たさない) 要素をコピーする

要素が処理終了間近になると、オーバーラップがなくなります。

編集

完全を期すために、上記のアルゴリズムの実装を次に示します。

private E[][] shift(E[][] input) {
    int maxLen = get2DMaxLen(input);
    int i_next = 0, j_next = 0;
    int i_least = input.length-1, j_least = maxLen-1;
    E[][] actual = new E[input.length][maxLen];
    for(int i = 0; i < input.length; i++) {
        for(int j = 0; j < input[i].length; j++) {
            if(meetsCondition(input[i][j])) {
                actual[i_least][j_least--] = input[i][j];
                if(j_least == -1) {
                    j_least = maxLen-1;
                    i_least--;
                }
            } else {
                actual[i_next][j_next++] = input[i][j];
                if(j_next == input[i].length) {
                    j_next = 0;
                    i_next++;
                }
            }
        }
    }
    return actual;
}

テスト入力

0 1 1 0 1 
0 1 1 1 0 
1 0 1 0 1 
1 1 0 1 1 
0 0 1 1 1

出力

1 1 1 1 1 
1 1 1 1 1 
1 1 1 1 1 
1 0 0 0 0 
0 0 0 0 0
于 2013-04-09T11:34:39.707 に答える
0

非効率的なバージョン:

  • すべての非 0 項目を格納する配列を反復処理します (たとえば、queueを使用して、 LinkedListでシミュレートできます)。

  • もう一度反復して、格納されたアイテムを 1 つずつ配列にプルするだけです。

次のようなイテレータ

for (int i = 0; i < arr.length; i++)
for (int j = 0; j < arr[i].length; j++)
  ...

より (スペース) 効率的なバージョン:

配列を同時に 2 回繰り返し、各値を読み取り、適切な場所に配置します。

擬似コード: (うまくいけば十分に読める)

while ahead.hasNext
  // skip all 0s
  do
    i = ahead.next
  while i == 0
  behind.writeNext(i)

// the rest must all be 0
while behind.hasNext
  behind.writeNext(0)

すべての作業を代行できないため、コードを提供できません。

于 2013-04-09T11:35:15.187 に答える