4

重複の可能性:
Java の値で Map<Key, Value> をソートする方法は?
Javaでマップ値をキーでソートする方法

スコアを追跡しようとしていますが、キーと値を外に出すことなく、スコアを昇順以外に並べ替えることができる必要があります。私の最初の考えは、マップを使用することでしたが、マップを値でソートしておく方法を見つけるのに本当に苦労しています。値はすべて Integer オブジェクトです。このようなハイスコアリストを並べ替えるにはどうすればよいですか?

4

1 に答える 1

1

これは、マイクロソフト/アマゾンの就職の面接タイプの質問です。優先キューを使用することも、キューの最初の要素として最高のスコアを使用することもできます。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検索/更新が必要な場合は、Java APIによるとO（1）です。

実装上の注意：この実装は、エンキューおよびデキューメソッド（offer、poll、remove（）、およびadd）にO（log（n））時間を提供します。remove（Object）メソッドとcontains（Object）メソッドの線形時間。検索メソッド（ピーク、要素、サイズ）の一定時間。

APIを読んでください。おそらく、を上書きするComparator<? super E> comparator()か、少なくとも必要に応じて変更する必要があると思います。それはそれをする必要があります。

于 2012-07-14T23:33:05.833 に答える