我在读这问题。所选答案包含以下两种算法。我不明白为什么第一个的时间复杂度为O（LN（N））。在最坏的情况下，如果阵列不包含任何重复它将循环n次所以没有第二个。我错了还是我失去了一些东西？谢谢

1）快（在极限）的方式

下面是一个基于散列的方法。你必须支付的自动装箱，但它是不是O（N2）O（LN（N））。一个积极进取的灵魂会去找到一个原始的INT-基于哈希集合（Apache或谷歌集合了这样的事情，记错。）

 布尔复印件（最终诠释[]拉链codeLIST）
{
  设置＆LT;整数GT;一次性=新的HashSet＆LT;整数GT;（）;
  对于（INT I：拉链codeLIST）
  {
    如果（lump.contains（I））回归真实;
    lump.add（ⅰ）;
  }
  返回false;
}
 

2）低头HuyLe

请参阅HuyLe的答案或多或少O（n）的解决方案，我认为需要几个add'l步骤：

 静态布尔复印件（最终诠释[]拉链codeLIST）{
    最终诠释MAXZIP = 99999;
    布尔[] =位新的布尔[MAXZIP + 1];
    java.util.Arrays.fill（位图，FALSE）;

    对于（INT项目：拉链codeLIST）
        （！位图[项目]），如果位图[项目] =真;
        否则返回true;
    }

    返回false;
}
 

解决方案

第一个解决方案应该已经预计为O（n）的复杂性，因为整个拉链code表必须经过，并处理每个拉链code是O（1）预期的时间复杂度。

即使考虑到在插入HashMap中可以触发重新散列，复杂度仍然是 O（1）。这有点不合逻辑的推论的，因为可能会出现的Java HashMap和在链路的假设之间没有关系，但它的存在表明它是可能的。

从 HashSet的文档：

本类报价常量时间的性能为基本操作（添加，删除包含和大小），假定哈希功能分散的元素之间正确的水桶。

这是同为第二个解决方案，这是正确的分析：O（N）

（只是一个题外话注意到，位集合比数组快，如在原岗位看出，自8 布尔 s的压缩到1 字节，它使用较少的内存）。

I was reading this question. The selected answer contains the following two algorithms. I couldn't understand why the first one's time complexity is O(ln(n)). At the worst case, if the array don't contain any duplicates it will loop n times so does the second one. Am I wrong or am I missing something? Thank you

1) A faster (in the limit) way

Here's a hash based approach. You gotta pay for the autoboxing, but it's O(ln(n)) instead of O(n2). An enterprising soul would go find a primitive int-based hash set (Apache or Google Collections has such a thing, methinks.)

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)Bow to HuyLe

See HuyLe's answer for a more or less O(n) solution, which I think needs a couple of add'l steps:

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; 
}

The first solution should have expected complexity of O(n), since the whole zip code list must be traversed, and processing each zip code is O(1) expected time complexity.

Even taking into consideration that insertion into HashMap may trigger a re-hash, the complexity is still O(1). This is a bit of non sequitur, since there may be no relation between Java HashMap and the assumption in the link, but it is there to show that it is possible.

From HashSet documentation:

This class offers constant time performance for the basic operations (add, remove, contains and size), assuming the hash function disperses the elements properly among the buckets.

It's the same for the second solution, which is correctly analyzed: O(n).

(Just an off-topic note, BitSet is faster than array, as seen in the original post, since 8 booleans are packed into 1 byte, which uses less memory).