java - Javaで一致した配列を並べ替える

Question

（Javaで）2つの配列があるとしましょう。

int[]番号; およびint[]色;

数字のi番目の各要素は、色のi番目の要素に対応しています。例：数字={4,2,1}色={0x11、0x24、0x01}; 番号4が色0x11、番号2が0x24などであることを意味します。

数値配列を並べ替えたいのですが、それでも各要素の色のペアと一致するように並べ替えます。

元。数字={1,2,4}; 色={0x01,0x24,0x11};

これを行うための最もクリーンで簡単な方法は何ですか？配列には数千のアイテムがあるため、配置するのが最適ですが、必須ではありません。Arrays.sort（）とカスタムコンパレータを実行するのは理にかなっていますか？可能な限りライブラリ関数を使用することをお勧めします。

注：「最善の」解決策は、2つの要素のクラスを作成し、カスタムコンパレータを使用することです。この質問は、これをコーディングする最も簡単な方法を人々に尋ねることを目的としています。プログラミング競技会に参加していると想像してみてください。これらすべての追加クラス、コンパレータ用の匿名クラスなどを作成したくないでしょう。さらに良いことに、Javaを忘れてください。Cでどのようにコーディングしますか？

score 20 · Accepted Answer

インデックス付きの 3 番目の配列を保持し、それを並べ替えて、データをそのままにしておく場合は、カスタムコンパレータで sort() を使用できます。

Java コード例:

Integer[] idx = new Integer[numbers.length];
for( int i = 0 ; i < idx.length; i++ ) idx[i] = i;              
Arrays.sort(idx, new Comparator<Integer>() {
    public int compare(Integer i1, Integer i2) {                        
        return Double.compare(numbers[i1], numbers[i2]);
    }                   
});

// numbers[idx[i]] is the sorted number at index i
// colors[idx[i]] is the sorted color at index i

Integerの代わりに使用する必要があるintか、カスタムコンパレータを使用できないことに注意してください。

score 8 · Accepted Answer

最もクリーンな方法は、Comparable を実装するカスタムプロパティクラスを作成することです。例えば：

class Color implements Comparable {
  private int number;
  private int color;

  // (snip ctor, setters, etc.)

  public int getNumber() {
    return number;
  }
  public int getColor() {
    return color;
  }

  public int compareTo(Color other) {
    if (this.getNumber() == other.getNumber) {
      return 0;
    } else if (this.getNumber() > other.getNumber) {
      return 1;
    } else {
      return -1;
    }
  }
}

次に、並べ替えアルゴリズムを順序付けロジックから分離できます (配列の代わりに List を使用する場合は Collections.sort を使用できます)。最も重要なことは、2 つの配列が同期しなくなることを心配する必要がないことです。

score 4 · Accepted Answer

余分なスペースを割り当てたい場合は、別の配列を生成し、次のような要素を追加して、それをエクストラと呼ぶことができます。

extra = [0,1,...,numbers.length-1]

次に、Arrays.sort() とカスタムコンパレータを使用して、この余分な配列を並べ替えることができます (つまり、要素 i と j を比較すると、数値 [extra[i]] と数値 [extra[j]] が実際に比較されます)。このように余分な配列を並べ替えた後、extra[0] には最小の数値のインデックスが含まれ、数値と色が移動しなかったため、対応する色が含まれます。
これはあまり良い方法ではありませんが、仕事は完了します。これ以上簡単な方法は思いつきません。

余談ですが、コンペティションでは、通常、C++ のテンプレートペアと素敵なマップが不可欠であることがわかります ;)

score 3 · Accepted Answer

@tovareのソリューションが好きです。ポインター配列を作成します。

int ptr[] = { 1, 2, 3 };

数値で並べ替えるときは、数値ではなく ptr で値を交換します。次に、次のように ptr 配列を介してアクセスします

for (int i = 0; i < ptr.length; i++)
{
   printf("%d %d\n", numbers[ptr[i]], colors[ptr[i]]);
}

更新: OK、他の人が私をこれに打ち負かしたようです. 私にはXPはありません。

score 3 · Accepted Answer

3 番目のインデックス配列の使用例。これが最適な実装かどうかはわかりません。



    import java.util.*;

public class Sort {

    private static void printTable(String caption, Integer[] numbers, 
                Integer[] colors, Integer[] sortOrder){

        System.out.println(caption+
                "\nNo   Num   Color"+
                "\n----------------");

        for(int i=0;i<sortOrder.length;i++){
            System.out.printf("%x    %d     %d\n", 
                    i,numbers[sortOrder[i]],colors[sortOrder[i]]);

        }
    }


    public static void main(String[] args) {

        final Integer[] numbers = {1,4,3,4,2,6};
        final Integer[] colors  = {0x50,0x34,0x00,0xfe,0xff,0xff};
        Integer[] sortOrder = new Integer[numbers.length];

        // Create index array.
        for(int i=0; i<sortOrder.length; i++){
            sortOrder[i] = i;
        }
        printTable("\nNot sorted",numbers, colors, sortOrder);

        Arrays.sort(sortOrder,new Comparator<Integer>() {   
            public int compare(Integer a, Integer b){
                return numbers[b]-numbers[a];
            }});
        printTable("\nSorted by numbers",numbers, colors, sortOrder);

        Arrays.sort(sortOrder,new Comparator<Integer>() {   
            public int compare(Integer a, Integer b){
                return colors[b]-colors[a];
            }});
        printTable("\nSorted by colors",numbers, colors, sortOrder);
    }
}

出力は次のようになります。

ソートされていません
ナンバーカラーなし
----------------
0 1 80
1 4 52
2 3 0
3 4 254
4 2 255
5 6 255

番号順
ナンバーカラーなし
----------------
0 6 255
1 4 52
2 4 254
3 3 0
4 2 255
5 1 80

色別に並べ替え
ナンバーカラーなし
----------------
0 6 255
1 2 255
2 4 254
3 1 80
4 4 52
5 3 0

score 3 · Accepted Answer

数値と色を表すオブジェクトを導入し、そのためのコンパレータ関数を実装してみませんか?

また、本当に配列が必要なのですか? Collection から派生したものを使用してみませんか?

score 2 · Accepted Answer

簡単なハックの 1 つは、2 つの配列をビットシフトで結合することです。最上位 32 ビットが数値で、最下位 32 ビットが色になるように long の配列を作成します。ソート方法を使用してから開梱します。

score 1 · Accepted Answer

独自のソート方法をコーディングするだけで十分でしょうか? 単純なバブルソートはおそらくすぐにコーディングできます (そして正しく動作します)。追加のクラスやコンパレータは必要ありません。

score 1 · Accepted Answer

@tovare元の最良の回答のクレジット。

以下の私の回答は、この回答から Maven 依存関係{net.mintern :primitive : 1.2.2}を介して (現在) 不要なオートボクシングを削除します: https://stackoverflow.com/a/27095994/257299

int[] idx = new int[numbers.length];
for( int i = 0 ; i < idx.length; i++ ) idx[i] = i;
final boolean isStableSort = false;
Primitive.sort(idx,
               (i1, i2) -> Double.compare(numbers[i1], numbers[i2]),
               isStableSort);

// numbers[idx[i]] is the sorted number at index i
// colors[idx[i]] is the sorted color at index i

score 0 · Accepted Answer

C でこれを行う最も簡単な方法は、バブルソート + デュアルポインターです。もちろん、最速はクイックソート + 2 つのポインターです。もちろん、2番目のポインターは2つの配列間の相関を維持します。

2 つの配列に格納されている値を構造体として定義し、その構造体を 1 つの配列で使用したいと思います。次に、クイックソートを使用します。比較関数を呼び出すことで、ソートの汎用バージョンを記述できます。これは、構造体ごとに記述することができますが、すでに知っています:)

score 0 · Accepted Answer

数値配列内の相対的な項目で色配列を並べ替える必要があります。数値を比較するコンパレータを指定し、それを色配列の比較として使用します。

score 0 · Accepted Answer

0

ツリーマップを使用する

于 2010-09-13T09:44:11.643 に答える

java - Javaで一致した配列を並べ替える

13 に答える 13

Related

Reference