如何排序索引映射回收集原始索引我整理

我有一個集合（名單<矩形>），我需要梳理左右。這部分很簡單。然後我想遍歷原始順序中的矩形，但很容易在排序後的集合中找到它們的索引。 indexOf（）將不起作用，因爲我可能有許多相同的對象。我不禁感到應該有一個簡單的方法來做到這一點。如何排序索引映射回收集原始索引我整理

來源

2008-10-16 Draemon

我已經找到了解決辦法 - 但也許有一個整潔的/更優化的一個在那裏。

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 */ 
...

來源

2008-10-16 00:29:25 Draemon

如果沒有對象數以萬計的，你可以只將它們存儲在兩個單獨的集合，一個原始的，一個排序。請記住，在Java中集合類只能存儲引用對象，所以這不會佔用盡可能多的內存，因爲它看起來。

來源

2008-10-16 00:06:32

這不是那麼簡單。假設我有這些集合（a和b）。如果我遍歷a，我怎麼在b中找到這個對象？我不能做indexOf（可能有兩個相等的矩形），而且無論如何這將是無效的。 – Draemon 2008-10-16 00:10:39

如果您正在通過排序集合進行搜索，只需將其作爲一個數組並進行二分搜索即可。O（lg n）。 – 2008-10-16 00:22:34

克隆的名單和他們的排序之一。由於指向同一個對象的指針是相同的，並且你不能在它們之間進行區分，所以使用indexOf（）對同一個對象進行兩次引用並不重要。如果你有兩個相同但不相同的對象，並且你想區分它們，那麼你確實有問題，因爲indexOf（）正在使用equal方法。在這種情況下，最好的解決方案可能是遍歷列表並檢查對象標識（==）。

來源

2008-10-16 00:16:53 eishay

另一種方法是對索引數組進行排序，而不是對原始列表進行排序。該數組以一個標識數組a [0] = 0，a [1] = 1等開始，然後使用自定義比較器/排序來獲取索引數組。不需要太多的額外空間，因爲您只有一個額外的整數數組而不是另一個集合。

來源

2008-10-16 01:32:55

如何排序索引映射回收集原始索引我整理

回答

相關問題