java - 在数字数组中查找重复数字

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

我想出了以下解决方案:

方法一:

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 是否有效？

根据我的理解，map 或 set 的时间复杂度比较小，HashSet 内部实现也是使用 HashMap 的。如何回答这个问题。

Answer 1

如果数字出现 3 次或更多次，则方法 2 会失败，因为它会将数字多次添加到输出中。您对更少的空间复杂度是正确的，但您的推理有点奇怪 - 这是因为 HashSet 将在其底层 HashMap 内部使用相同的虚拟对象来指示存在值，而对于 Approach1，您正在分配一个 Integer每次。

HashMap 内部保存了一个桶列表，所以一般来说，如果你能够分配一个包含一百万个数字的列表，你也应该能够分配一个 HashMap 保存(最多)尽可能多的数字。

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

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