如何将排序后的索引映射回我正在排序的集合的原始索引

Question

我有一个集合（List <！> lt; Rectangle <！> gt;），我需要左右排序。那部分很容易。然后我想以原始顺序遍历矩形，但很容易在已排序的集合中找到它们的索引。 indexOf（）不起作用，因为我可能有许多相等的对象。我不禁觉得应该有一个简单的方法来做到这一点。

Answer 1

我找到了一个解决方案 - 但也许有一个更整洁/更优化的解决方案。

List<Rectangle> originalRects = ...;

/* record index of each rectangle object.
 * Using a hash map makes lookups efficient,
 * and using an IdentityHashMap means we lookup by object identity
 * not value.
 */
IdentityHashMap<Rectangle, Integer> originalIndices = new IdentityHashMap<Rectangle, Integer>();
for(int i=0; i<originalRects.size(); i++) {
    originalIndices.put(originalRects.get(i), i);
}

/* copy rectangle list */
List<Rectangle> sortedRects = new ArrayList<Rectangle>();
sortedRects.addAll(originalRects);

/* and sort */
Collections.sort(sortedRects, new LeftToRightComparator());

/* Loop through original list */
for(int i=0; i<sortedRects.size(); i++) {
    Rectangle rect = sortedRects.get(i);
    /* Lookup original index efficiently */
    int origIndex = originalIndices.get(rect);

    /* I know the original, and sorted indices plus the rectangle itself */
...

Answer 2

如果你没有成千上万的对象，你可以将它们存储在两个独立的集合中，一个是原始的，一个是有序的。请记住，Java中的集合类只将引用存储到对象中，因此这不会占用尽可能多的内存。

Answer 3

克隆列表并对其中一个进行排序。使用同一个对象的两个引用对indexOf（）来说并不重要，因为指向同一个对象的指针是相同的，你无法在它们之间分辨。 如果你有两个相同但不相同的对象，并且你想要区分它们，那么你确实遇到了问题，因为indexOf（）使用的是相等的方法。 在这种情况下，最好的解决方案可能是简单地遍历列表并检查对象标识（==）。

Answer 4

另一种方法是对索引数组进行排序，而不是对原始列表进行排序。数组以身份数组a [0] = 0，a [1] = 1等开始，然后使用自定义比较器/排序来获取索引数组。不需要太多额外空间，因为你只有一个额外的整数数组而不是另一个集合。