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，而不是 aNumber和Comparable）。它也不太灵活，并且由于其性质，您可以明确保证在键和值之间具有一对一的映射。

于 2014-03-14T03:18:34.860 回答