我有List<Element<Integer, Integer>>類型，其中每個元素包含兩個整數，一個ENTITYID &另一個的優先級是該實體的列表。現在我需要創建一個entityIds的數組Integer[]，這個數組已經根據Element對象中爲每個實體提供的優先級進行了排序。建築陣列（在一個ArrayList內的對象定義）

我有權訪問，只有列表的迭代器。創建這種優先級排序的entityIds數組的最佳方式是什麼？

我的想法：

使用迭代器首先創建元素的數組，使用優先使用Arrays.sort() &然後創建整數&的新數組複製從排序數組的entityIds對它們進行排序。這是一個好主意嗎？或者還有比這更好的替代方案嗎？

來源

2012-04-26 Rajat Gupta

把你的名單分成了比較，着眼於優先級一個PriorityQueue;然後迭代優先級隊列並收集數組。

未經測試的代碼如下;請隨時解決錯別字。

Integer[] getSortedEntityIds(Iterator<Element<Integer, Integer>> iter) { 
    Comparator<Element<Integer,Integer>> comp = new Comparator<Element<Integer, Integer>>() { 
    @Override 
    public int compare(Element<Integer,Integer> ela, Element<Integer,Integer> elb) { 
     return ela.getPriority().compareTo(elb.getPriority()); 
    } 
    }; 

    PriorityQueue<Element<Integer,Integer>>pq = new PriorityQueue<Element<Integer,Integer>>(256, comp); 
    // If you had the access to the whole list, you wouldn't have to iterate, you could just pass it into the pq constructor 
    while(iter.hasNext() { 
    pq.add(iter.next()); 
    } 

    Integer[] sortedEntityIds = new Integer[pq.size()] 

    for(int i = 0; i < pq.size(), i++) { 
    Element<Integer, Integer>el = pq.remove(); 
    sortedEntityIds[i] = el.getEntityId(); 
    } 

    return sortedEntityIds; 
}

來源

2012-04-26 04:48:54 ykaganovich

什麼只是把它在一個數組和使用Arrays.sort（）呢？ – 2012-04-26 05:04:05

那麼，除非你知道原始列表的大小（你說你只有一個迭代器），否則你不能將它們放入數組中。您可以將它們添加到列表中，然後對其進行排序;我認爲這相當於將它們添加到PriorityQueue ... – ykaganovich 2012-04-26 05:18:50

是的，但實際上我確實知道大小不知何故.. – 2012-04-26 05:20:09

創建第二個列表。
從原始列表中獲取下一個項目。
遍歷第二個列表並查找具有更高優先級的第一個項目。
在它之前插入當前項目。
轉到2或結束。

來源

2012-04-26 04:47:39 Yarg

我的列表是大型（16000）因此我不能選擇那種有n^2的複雜性 – 2012-04-26 04:52:00

您可以使用自定義比較器在您認爲合適的任何方式列表元素進行排序。

final List<Element<Integer, Integer>> list = new ArrayList<Element<Integer, Integer>>(); 
list.add(new Element<Integer, Integer>(1, 1)); 
list.add(new Element<Integer, Integer>(4, 4)); 
list.add(new Element<Integer, Integer>(3, 3)); 
list.add(new Element<Integer, Integer>(2, 2)); 
list.add(new Element<Integer, Integer>(5, 5)); 

Collections.sort(list, new Comparator<Element<Integer, Integer>>() { 

    @Override 
    public int compare(final Element<Integer, Integer> x, 
      final Element<Integer, Integer> y) { 
     return x.getPriority().compareTo(y.getPriority()); 
    } 
}); 

// Prints elements in ascending order of priority 
System.out.println(Arrays.toString(list.toArray()));

來源

2012-04-26 04:54:57 hoipolloi

建築陣列（在一個ArrayList內的對象定義）

我的想法：

回答

相關問題