Java中HashMap.containvalue（）的时间复杂度是多少？

performance optimization hashmap java

2022-09-01 13:08:03

我得到了一个时间复杂度的问题要解决：O(n)

“给定一个数字和数字x的列表。查找列表中是否有任何 2 个数字加起来等于 x？

这是我的解决方案：

public class SumMatchResult {

  public static void main(String[] args){
    int[] numberList = {6,1,8,7,4,6};
    int requiredSum = 8;
    boolean isSumPresent = checkSumPresentHash(numberList,requiredSum);
    if(isSumPresent) {
      System.out.println("Numbers exist");
    }else {
      System.out.println("Numbers donot exist");
    }
  }

  private static boolean checkSumPresentHash(int[] numberList, int requiredSum) {
    Map<Integer, Integer> m = new HashMap<Integer,Integer>();
    int count = 0;
    for(int i=0;i<numberList.length;i++){
      m.put(i, numberList[i]);
    }
    for(int i=0;i<numberList.length;i++){
      if(m.containsValue(requiredSum - numberList[i])){
        count++;
      }
    }
    if(count>1){
        return true;
    }
    return false;
  }

}

我正在使用而不是使用一个肯定具有复杂性的因为，我必须考虑我的输入可能包含相同值的情况。例如，在上面的例子中，我可以有一组要匹配的输入值，它应该返回。HashMap.containsValue()HashSet.contains()O(1){3,6,4,4,7}sum 8true

我上面的解决方案的时间复杂度取决于方法的复杂程度。请对方法的时间复杂度进行一些阐明，并建议我在时间复杂度方面是否有更好的解决方案来解决上述问题。谢谢。HashMap.containsValue()containsValue()

答案 1

要回答标题中的问题 - 正如其他人所提到的，是O（n），因为没有键，它就不知道它在哪里，算法必须遍历地图中存储的所有值。containsValue

要回答问题正文中的问题 - 关于如何解决它 - 只需考虑一下您是否真的需要一个通用地图，该地图可以计算您看到每个数字的实例数。我的意思是，你唯一关心一个数字是否出现不止一次的时候是当它是x/2的时候，对吧？对我来说，这闻起来像一个角落案例。只需添加一个测试来检查该极端情况 - 例如在集合构造循环期间嵌入，然后在它之后（请参阅下面的其他变体）。if (numberList[i] == requiredSum/2) half++if (requiredSum % 2 == 0 && half == 2) return true

然后，您可以只循环访问该集，并针对每个项目检查该集是否也出现在该集中。requiredSum-item

总结一下（如果可能的话，提前退出）：

Set<Integer> seen = new HashSet<Integer>();
boolean halfSeen = false;
for (int num : numberList) {
    if (num == requiredSum/2 && requiredSum % 2 == 0) {
        if (halfSeen) return true;
        halfSeen = true;
    } else {
        seen.add(num);
    }
}
for (int num : seen) {
    if (seen.contains(requiredSum - num)) return true;
}
return false;

答案 2

HashMap本质上是一个键值存储，可以访问它的密钥，复杂程度为O（1）。但是，检查值后，HashMap除了检查所有值并查看它们是否等于您正在搜索的值之外，什么也做不了。因此，复杂度为 O（n），其中 n 是 HashMap 中的元素数。

另一方面：您正在其盒装类型（Integer）的集合中查找基元值（int）。这意味着每次在 HashMap 上调用方法时，Java 都需要将基元值框起来：http://docs.oracle.com/javase/1.5.0/docs/guide/language/autoboxing.html