java - LinkedHashMap 复杂度

Question

我有一个简单的问题来找到数组 A 中的第一个唯一元素。但是，令我困扰的是使用不同方法的时间复杂度。到目前为止，我已经尝试过这两种方法。

第一种方法:

LinkedHashMap<Integer, List<Integer>> map = new LinkedHashMap<Integer, List<Integer>>();
for (int i = 0; i < A.length; i++)
{
    if (!map.containsKey(A[i]))
        map.put(A[i], new ArrayList<>());
    map.get(A[i]).add(i);
}

for (Map.Entry<Integer, List<Integer>> m : map.entrySet())
    if (m.getValue().size() == 1)
        return m.getKey();
return -1;

第二种方法:

    for(int i=0; i< A.length; i++){
        boolean unique = true;
        nestedFor:for(int j=0; j< A.length; j++){
            if(i != j && A[i] == A[j]){
                unique = false;
                break nestedFor;
            }
        }
        if(unique)
            return A[i];
    }
    return -1;

测试包含 1000000 个元素的数组，第一个方法执行时间约为 2000 毫秒，而第二个方法执行时间约为 10 毫秒。我的问题是:与复杂度为 O(n^2) 的第二种方法相比，第一种方法的复杂度是 O(nLogn)，难道不应该执行得更快吗？我在这里错过了什么？测试代码下方:

    int[] n = new int[1000000];
    for (int i = 0; i < n.length; i++)
        n[i] = new Random().nextInt(2000000);

    long start = System.currentTimeMillis();
    firstUnique(n);
    System.err.println("Finished at: " + (System.currentTimeMillis() - start ) + "ms");

编辑:

for (int i = 0; i < A.length; i++)
{
    if (!map.containsKey(A[i]))
        map.put(A[i], new ArrayList<>());
    map.get(A[i]).add(i);
}

消耗了 99% 的执行时间，而

for (Map.Entry<Integer, List<Integer>> m : map.entrySet())
    if (m.getValue().size() == 1)
        return m.getKey();

始终为 1-3 毫秒。所以，是的，填充 map 是最昂贵的操作。

对于此类问题，您认为最有效的方法是什么？

Answer 1

我怀疑您没有选择为第二种情况创造“最坏情况”条件的输入。

例如，如果您构建数组，使得所有百万个元素都有重复项(例如 A[i] = 2 * i/A.length)，那么第二种方法是，比第一个慢得多，因为它必须检查元素的 10^12 组合。

您可以通过将内部 for 循环的条件更改为仅从 j = i + 1 检查，但 10^12/2 仍然是一个很大的数字。

如果您只是简单地选择随机数来填充数组，那么第一个元素很可能是唯一的，并且第一个和第二个元素中的一个是唯一的可能性更大，等等。在几个元素之后，您将几乎确定该元素是唯一的，因此它会在几次迭代后停止。

---

第一种方法花费的 2 秒太长了。我只能认为您在基准测试之前没有正确预热 JIT。但即使不尝试这样做，您的第一种方法对我来说也只需要 40-50 毫秒(几次迭代后下降到 10-15 毫秒)。

大部分时间将归因于对象创建 - 在键和值的自动装箱以及 ArrayList 实例的创建中。