0

整数 ID のリストがあります。このリストがArrayList<Integer>またはint []であるとしましょう。それは問題ではありません。最初のリストのように同じ ID を持つオブジェクトを含む別のArrayList<Obj>ものがありますが、それらは異なる順序で並べられています。

2 番目のリストのオブジェクトを、最初のリストの ID の順序で並べたいと思います。

例：

FIRST LIST:  { 1, 5, 4, 8, 6 }
SECOND LIST: { Obj[id=5], Obj[id=8], Obj[id=6], Obj[id=1], Obj[id=4] }

RESULT LIST: { Obj[id=1], Obj[id=5], Obj[id=4], Obj[id=8], Obj[id=6] }

誰かがこれを行う（効率的な）方法を教えてもらえますか?

4

3 に答える 3

3

地図を使用することをお勧めします：

Map<Integer, Obj> map = new HashMap<Integer, Obj>(secondList.size() * 2);
for (final Obj obj : secondList) {
    map.put(obj.id, obj);
}
for (int i = 0; i < secondList.size(); i++) {
    secondList.set(i, map.get(firstList.get(i)));
}

これは O(n) で実行されますが、これは私見が得ることができる最高のものです。

于 2013-10-02T09:15:46.923 に答える
1

A/ 次のような、一致する ID インデックス リストを作成します。

1 -> 0
5 -> 1
4 -> 2
8 -> 3
6 -> 4

これは、最初のリストの逆参照です。各idの位置を示します。SparseIntArray は、それを行う良い方法です。

SparseIntArray ref = new SparseIntArray();
for (int i = 0; i < firstList.size(); i++) {
    ref.append(firstList.get(i), i);
}

次に、オブジェクトの ID と参照テーブルを使用する Comparator を使用して、2 番目のリストを並べ替える必要があります。

Collections.sort(secondList, new Comparator<Obj>() {
    public int compare(Obj t1, Obj t2) {
        return ref.get(t1.id) - ref.get(t2.id);
    }
});
于 2013-10-02T09:14:02.087 に答える
0

彼が投稿したとき、私はエティエンヌの答えを書いている最中だったので、楽しみのために、オブジェクトを作成しない、より小さな定数係数を持つ O(N^2) ソリューションを次に示します。

    int[] first = { 1, 5, 4, 8, 6 };
    Obj[] second = { Obj[id=5], Obj[id=8], Obj[id=6], Obj[id=1], Obj[id=4] };
    int i = 0;
    while(i < second.length) {
        int ind = -1;
        for(int j=0;j<first.length;j+=1) {
            if(first[j] == second[i].id) {
                ind = j;
                break;
            }
        }
        if(ind == -1) break; //Bad news
        if(ind == i) {
            i += 1;
        } else {
            Obj temp = second[i];
            second[i] = second[ind];
            second[ind] = temp;
        }
     }

明らかに、second[] の作成は疑似コードですが、配列が同じ長さである場合、残りは機能します。非常に小さなデータセットの場合、これは Etienne のものよりも少し高速になると思いますが、両方の答えをプロファイリングする必要があります。

于 2013-10-02T09:38:00.787 に答える