在一个数字数组中查找重复的数字

Question

我在面试中被问到这个问题，给定一个数字列表，只返回输入中存在的重复数字作为排序后的输出。

例如：

Input = [6, 7, 5, 6, 1, 0, 1, 0, 5, 3, 2]
Output = [0, 1, 5, 6] - sorted unique numbers which are duplicates in input

我想出了以下的解决方案：

方法1：

public static List<Integer> process(List<Integer> input) {
    List<Integer> result = new ArrayList<>();
    Map<Integer, Integer> map = new HashMap<>();
    for (int val : input) {
        map.put(val, map.getOrDefault(val, 0) + 1);
    }

    map.forEach((key, val) -> {
        if (val > 1) {
            result.add(key);
        }
    });
    result.sort(null);
    return result;
}

更新方法2：

public static List<Integer> process1(List<Integer> input) {
    Set<Integer> dups = new HashSet<>();
    Set<Integer> set = new HashSet<>();
    for (int val : input) {
        if (set.contains(val)) {
            dups.add(val);
        } else {
            set.add(val);
        }
    }
    List<Integer> result = new ArrayList<>(dups);
    result.sort(null);
    return result;
}

旧方法2

public static List<Integer> process1(List<Integer> input) {
    List<Integer> result = new ArrayList<>();
    Set<Integer> set = new HashSet<>();
    for (int val : input) {
        if (set.contains(val)) {
            result.add(val);
        } else {
            set.add(val);
        }
    }
    result.sort(null);
    return result;
}

方法1的时间复杂度为(n)Log(n)，因为在Java中排序是nlogn，空间复杂度为n。

方法2的时间复杂度再次为(n)Log(n)，因为在Java中排序是nlogn，空间复杂度比方法1少一些，因为我只在集合中保存元素一次。

如果我在找出时间和空间复杂度方面有错误，请纠正我。

现在的问题是，如果输入包含数百万个数字，这种逻辑是否有效？如果输入是数百万个数字，HashMap是否有效？

据我所知，通常情况下，映射或集合的时间复杂度较低，而HashSet的内部实现使用HashMap。如何回答这个问题？

- learner

---

我运行了你的两种方法，似乎Approach1可行，但是Approach2返回了错误的结果（列表中有多个相同的数字）。请注意，我在大小为10的简单列表上运行了这两个方法。 - Nexevis

@Nexevis，请问你可以分享一下输入数据吗？ - learner

当您至少有3个相同的输入时，它会中断，例如{1,1,1}将返回一个列表1, 1。 - Nexevis

可能是在非常大的数组中查找重复项的算法的重复问题。 - Oleksandr Pyrohov

@Nexevis，谢谢，我已经更新了代码。 - learner

请参见 https://docs.oracle.com/javase/tutorial/collections/interfaces/set.html 结尾。 - Robert

Answer 1

如果一个数字出现三次或更多次，Approach2就会失败，因为它会将该数字多次添加到输出中。关于空间复杂度较小的观点是正确的，但你的推理有些奇怪——这是因为HashSet在其底层HashMap中内部使用相同的虚拟对象来指示存在一个值，而对于Approach1，每次都要分配一个Integer。

HashMap在内部持有一个桶列表，因此通常，如果您能够分配一个包含一百万个数字的列表，那么您也应该能够分配一个最多容纳同样数量数字的HashMap。

在构建HashMap时将其初始容量设置为列表的大小是一个好主意。对于大型列表，这将使您的代码更快，因为它避免了重新哈希。

请注意可能有一种更快的方法：对初始列表进行排序。在排序后的列表中，查找重复项非常简单，因为它们是相邻的，因此您不需要HashMap。然而，如果您不允许修改它，则需要复制初始列表，因此空间要求将保持不变。理论复杂度保持不变（排序是O(nlogn)，查找重复项将是O(n)），实际排序时间会更长，因为我们对大型列表进行排序，但您将避免在HashMap中进行所有分配。这可能会弥补额外的排序大型列表所花费的时间，也可能不会。

- flyx

Answer 2

我很好奇在JMH性能测试下不同的算法实现会有怎样的表现，而我想出来的最快实现是：

Set<Integer> all = new HashSet<>(input.size());
Set<Integer> output = new TreeSet<>();

for(Integer val : input) {
   if (!all.add(val)) {
      output.add(val);
   }
}

return new ArrayList<>(output);

以下是针对上述实现（algo2）和你的方法1实现（algo1）的JMH结果：

Benchmark                   (N)  Mode  Cnt    Score    Error  Units
PerformanceTests.algo1  1000000  avgt    3  323.265 ± 33.919  ms/op
PerformanceTests.algo2  1000000  avgt    3  285.505 ± 29.744  ms/op

---

更新，@josejuan 你是正确的，下面是比以前快6倍的算法：

int[] input = new int[INPUT.size()];
for (int i = 0; i < input.length; i++) {
    input[i] = INPUT.get(i);
}
Arrays.sort(input);

List<Integer> output = new ArrayList<>(input.length);
int prev = input[0];
boolean added = false;
for (int i = 1; i < input.length; i++) {
    if (prev == input[i]) {
        if (!added) {
            output.add(prev);
            added = true;
        }
    } else {
        added = false;
        prev = input[i];
    }
}
return output;

- Adam Siemion

---

all.add(val) adds to all - Adam Siemion

你是对的（抱歉），使用两个哈希集合可以获得更好的性能（并在列表转换后进行排序）。 - josejuan

这是问题RANDOM.nextInt()使用低值RANDOM.nextInt(0, 1000)，那么没有树更快，只是有时候。 - josejuan

（更快的方法是将其转换为int []，进行排序并遍历） - josejuan

实际上，只有在低概率碰撞的情况下，树才比两个哈希表更快。 - josejuan