2

我正在阅读这个问题。所选答案包含以下两种算法。我不明白为什么第一个的时间复杂度是 O(ln(n))。在最坏的情况下，如果数组不包含任何重复项，它将循环 n 次，第二个也是如此。我错了还是我错过了什么？谢谢

1）更快（在极限）的方式

这是一种基于哈希的方法。您必须为自动装箱付费，但它是 O(ln(n)) 而不是 O(n2)。一个有进取心的人会去寻找一个原始的基于 int 的哈希集（Apache 或 Google Collections 有这样的东西，我想。）

boolean duplicates(final int[] zipcodelist)
{
  Set<Integer> lump = new HashSet<Integer>();
  for (int i : zipcodelist)
  {
    if (lump.contains(i)) return true;
    lump.add(i);
  }
  return false;
}

2）向惠勒鞠躬

请参阅 HuyLe 的答案以获得或多或少的 O(n) 解决方案，我认为这需要几个附加步骤：

static boolean duplicates(final int[] zipcodelist) {    
    final int MAXZIP = 99999;    
    boolean[] bitmap = new boolean[MAXZIP+1];    
    java.util.Arrays.fill(bitmap, false);    

    for (int item : zipcodeList)
        if (!bitmap[item]) bitmap[item] = true;
        else return true;    
    }

    return false; 
}
4

1 回答 1

2

第一个解决方案应该具有 O(n) 的预期复杂度，因为必须遍历整个邮政编码列表，并且处理每个邮政编码的预期时间复杂度是 O(1)。

即使考虑到插入 HashMap 可能会触发重新散列，复杂度仍然是O(1)。这有点不合理，因为 Java HashMap 与链接中的假设之间可能没有关系，但它表明这是可能的。

来自HashSet文档：

此类为基本操作（添加、删除、包含和大小）提供恒定的时间性能，假设哈希函数将元素正确地分散在桶中。

正确分析的第二个解决方案也是如此：O(n)。

（只是一个题外话，BitSet 比数组快，如在原始帖子中所见，因为 8 booleans 被打包成 1 byte，它使用更少的内存）。

于 2012-06-23T02:26:45.583 回答