哈希表反向查找找到最小密钥

我有一个面试问题来搜索哈希表中的值并返回最小的密钥。哈希表反向查找找到最小密钥

我的方法是按键对哈希表进行排序，并遍历它以找到与搜索值对应的键。

我写在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中做同样的事情？

来源

2014-03-14 Ramya

你会更好地通过所有的键进行线性搜索，并记录最大值而无需排序，因为排序将采用'Theta（nlogn）'。 –

[看起来像] [1]你需要一个外部库来用Java来完成它。 [1]：https://stackoverflow.com/questions/1670038/does-java-have-a-hashmap-with-reverse-lookup?rq=1 – Acapulco

@ C.B。那里有一点。 – Acapulco

我愿意打赌你可以，如果你可以保证你检查什么，以及你的钥匙是什么类型，是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; 
}

番石榴offers BiMap，其可以是更有用真实世界的情况下;但是，如果不覆盖它们，它将不允许存在重复值。

下面是一个例子。

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

这是一个很大的更简洁，并与前一个没有不需要的同类仿制药的（这一个只需要一个Number，不同时为Number和Comparable）。它也不太灵活，并且由于其本质，您明确保证在键和值之间具有一对一映射。

来源

2014-03-14 03:18:34 Makoto

搜索项不是最小的键吗？如果是这种情况，那么不需要searchItem。只需返回排序数组中的第一个元素（如果您显然将最小值排序为最大值），不是吗？另一方面，如果您确实需要搜索特定项目，则二进制搜索会更快，毕竟它已经排序。 – Acapulco

不一定。如果你不使用'BiMap'，并且你有两个相同的值，你需要找到第一次出现的关键字。这并不总是保证它是第一个元素;如果我的搜索项目是300，其关键编号结果是127和133，那么127是正确的答案。 – Makoto

这是真的。但是如何使用二进制搜索而不是线性搜索？ – Acapulco

哈希表反向查找找到最小密钥

回答

相关问题