0

我有整数 ID 列表。可以说这个列表是ArrayList<Integer>或 int[]，没关系。我有另一个ArrayList<Obj>包含与第一个列表中相同的 id 的对象，但它们以不同的顺序排列。

我想将第二个列表中的对象按第一个列表中的 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的位置。A SparseIntArray 是一种很好的方法：

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

然后，您需要使用使用 Object 的 id 和 ref 表的 Comparator 对第二个列表进行排序：

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

当他发布它时，我正在写 Etienne 的答案，所以为了好玩，这里有一个 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 回答