java中HashMap.containsValue()的时间复杂度是多少？

Question

我在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 8,应该返回true.

我上面的解决方案的时间复杂度取决于HashMap.containsValue()方法的复杂性.请详细说明containsValue()方法的时间复杂度,并建议我在时间复杂度方面是否有更好的解决方案来解决上述问题.谢谢.

Answer 1

要回答标题中的问题 - 正如其他人所提到的那样,containsValue是O(n),因为没有密钥它不知道它在哪里,算法必须遍历存储在地图中的所有值.

要回答问题正文中的问题 - 关于如何解决它 - 只要考虑一下您是否真的需要一个可以计算每个数字看到多少个实例的通用地图.我的意思是,唯一一次你关心的是,如果一个数字的外观不止一个是x/2,那么对吗？那对我来说就像一个角落的味道.只需添加一个检查该角落情况的测试 - 例如if (numberList[i] == requiredSum/2) half++在您的set-construction循环中嵌入,然后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;

Answer 2

HashMap本质上是一个键值存储,它可以访问复杂度为O(1)的密钥.但是,检查一个值,HashMap无法做任何事情,但检查所有值并查看它们是否与您正在搜索的值相等.因此,复杂度为O(n),其中n是HashMap中元素的数量.

另一方面:您正在查找其盒装类型(整数)集合中的原始值(int).这意味着每次在HashMap上调用方法时,Java都需要为您提供原始值:http://docs.oracle.com/javase/1.5.0/docs/guide/language/autoboxing.html