4

ハッシュ テーブルで値を検索し、最小のキーを返すというインタビューの質問がありました。

私のアプローチは、ハッシュテーブルをキーでソートし、それを繰り返し処理して、検索された値に対応するキーを見つけることでした。

この関数を Python で書きました。

def smallestKey(x):
    my_dict = {10:20, 5:30, -2:25, 1:20}
    for key in sorted(dict.iterkeys()):
        if (my_dict[key] == x):
            print key

より良いアプローチはありますか？Javaで同じことを行うにはどうすればよいですか?

4

1 に答える 1

1

チェックしているものとキーのタイプがNumber.

これがコードサンプルです。ソートには O(n log(n)) のコストがかかり、線形検索は O(n) であるため、このパフォーマンスは約 O(n log(n)) です。

public <K extends Number & Comparable<K>, V extends Number> K findSmallestKey(Map<K, V> values, V searchItem) {
    // Grab the key set, and sort it.
    List<K> keys = new ArrayList<>(values.keySet());
    Collections.sort(keys);
    for(K key : keys) {
        if(values.get(key).doubleValue() == searchItem.doubleValue()) {
            return key;
        }
    }
    return null;
}

Guavaは を提供していますBiMap。これは、より使いやすい実世界のケースかもしれません。ただし、上書きせずに重複した値が存在することは許可されません。

その例を次に示します。

public <K extends Number, V extends Number> K findSmallestKeyWithBimap(BiMap<K, V> values, V searchItem) {
    return values.inverse().get(searchItem);
}

これははるかに簡潔であり、前のものと同じ種類のジェネリックは必要ありません (これはaとNumberの両方ではなく、 a のみである必要があります)。また、柔軟性が大幅に低下し、その性質上、キーと値の間で 1 対 1 のマッピングが明示的に保証されます。NumberComparable

于 2014-03-14T03:18:34.860 に答える