什麼數據結構應該用於高分列表？

可能重複：
How to sort a Map<Key, Value> on the values in Java?
how to sort Map values by key in Java 什麼數據結構應該用於高分列表？

我試圖跟蹤得分，我需要能夠沒有得到密鑰的成績進入非升序排序並且不符合數值。我的第一個想法是使用地圖，但我真的很難找到一種方法來保持按值排序的地圖。這些值都是整數對象。我將如何去排序這樣的高分榜？

2012-07-14 SaxSalute

這個職位似乎描述您的問題： [http://stackoverflow.com/questions/109383/how-to-sort-a-mapkey-value-on-the-values-in-java] [1] [1]：http://stackoverflow.com/questions/109383/how-to-sort-a-mapkey-value-on-the-values-in-java – EdgeCase 2012-07-14 23:39:56

這是一個微軟/亞馬遜工作面試類型的問題。您可以使用優先級隊列作爲隊列的第一個元素，以獲得最高分數。創建一個節點作爲key | value對。按關鍵順序由分數值維護並實現隊列來實現它。

提供更多的細節

這是您的Node實現：

public class Node{ 

    private String name;  // the name 
    private double score;  // assuming you're using double 

    public Node(String name, double score){ 
     this.name = name; 
     this.score = score;   // assuming negative scores are allowed 
    } 
    public void updateScore(double score){ 
     this.score += score; 
    } 
}

而當你使用PriorityQueue，使Comparison根據得分值。如果你需要搜索/更新，它是O（1），根據Java API：

實現注意事項：此實現爲提供O（日誌（n））的時間入隊和dequeing方法（報價， poll，remove（）和add）; 線性時間爲remove（Object）和contains（Object）方法;和檢索方法的恆定時間（peek，element和size）。

閱讀API，我猜你可能需要覆蓋Comparator<? super E> comparator()，或至少修改它以滿足您的需求。這應該做到這一點。

來源

2012-07-14 23:33:05 cybertextron

這是一個有關排序地圖的問題。 PriorityQueue如何相關？ – Bohemian 2012-07-14 23:37:01

@Bohemian不，不是。這是一個關於哪種數據結構最適合這項工作的問題。 OP簡單地解釋說他使用地圖，而不是他_wants_基於地圖的解決方案。 – kba 2012-07-14 23:39:02

我對如何使用PriorityQueue來排序整數值的同時仍然保持字符串的位置感到有點困惑。 – SaxSalute 2012-07-14 23:45:46

什麼數據結構應該用於高分列表？

回答

相關問題