29

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()肯定具有复杂性的 a，O(1)因为我必须考虑我的输入可能包含相同值的情况。例如，在上述情况下，我可以有一组输入值{3,6,4,4,7}来匹配sum 8，它应该返回true。

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

4

4 回答 4

23

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

要回答问题正文中的问题 - 关于如何解决它 - 只需考虑您是否真的需要一张通用地图，该地图可以计算您看到每个数字的实例数。我的意思是，如果一个数字出现不止一次，你唯一会关心的是它是 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;
于 2013-05-26T08:47:06.300 回答
14

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

于 2013-05-26T08:12:42.753 回答
4

HashMap.containsValue 复杂度为 O(n)。但是 n 不完全是映射大小，而是哈希表大小，因为即使映射大小 = 0， containsValue 也会遍历所有表元素。假设我们创建了一个初始容量 = 1024 的空映射。 containsValue 必须遍历 1024 个元素的哈希表数组：

public boolean containsValue(Object value) {
    if (value == null)
        return containsNullValue();

    Entry[] tab = table;
    for (int i = 0; i < tab.length ; i++)
        for (Entry e = tab[i] ; e != null ; e = e.next)
            if (value.equals(e.value))
                return true;
    return false;
}
于 2013-05-26T08:32:25.913 回答
0

没有任何索引标记为 中的任何值HashMap，因此，要使用 查找值containsValue()，您必须遍历 的所有值HashMap。

请注意，O(n)这里的复杂性是 HashMap 中值的数量，而不是我们通常用来表示其复杂性的键/大小。

于 2021-07-31T07:13:18.840 回答