java - 在堆有限的列表中查找重复项

Question

有一个 N + 1 长度的只读列表，由 1 到 N 之间的数字组成。列表中有一个重复的项目，但可能还有更多。例如 N=3，列表项 [1,3,1,3]我需要一种打印重复项目的算法。(不管一个项目在其中有多少次)基于上面的例子，结果是 1,3我需要一个在 Java 中使用 limeted 堆的解决方案(可以在短时间内运行许多项目)

我尝试创建一个新的 HashSet 并将列表中的项目添加到集合中，如果它已经包含该项目，我已将其保存到 ArrayList。

public static void main(String[] args) {
    List<Integer> list = new ArrayList<>();

    list.add(1);
    list.add(2);
    list.add(3);
    list.add(4);
    list.add(1);
    list.add(2);
    list.add(5);

    Set<Integer> set = new HashSet();
    List<Integer> duplicatedList = new ArrayList<>();   

    for (Integer item : list) {
    if(set.contains(item)) {
        duplicatedList.add(item);
    }
    set.add(item);
}
System.out.println(duplicatedList +" "+ list);

它有效，但我认为这不是太有效。对于这个问题，有没有更有效的解决方案？

Answer 1

如果您想要限制堆使用，请从原始列表中删除非重复项，而不是创建新列表。也可以使用 BitSet 跟踪已经看到的数字。

List<Integer> list = new ArrayList<>(Arrays.asList(1,2,3,4,1,2,5));
int N = list.size() - 1;

BitSet present = new BitSet(N);
for (Iterator<Integer> iter = list.iterator(); iter.hasNext(); ) {
    int value = iter.next();
    if (! present.get(value)) {
        present.set(value);
        iter.remove();
    }
}
System.out.println(list);

输出

[1, 2]

如果原始列表是只读的，则像问题一样构建一个新列表。

List<Integer> list = Arrays.asList(1,2,3,4,1,2,5);

BitSet present = new BitSet();
List<Integer> duplicatedList = new ArrayList<>();
for (Integer item : list) {
    if (present.get(item))
        duplicatedList.add(item);
    else
        present.set(item);
}
System.out.println(duplicatedList +" "+ list);

输出

[1, 2] [1, 2, 3, 4, 1, 2, 5]

主要改进是使用BitSet而不是 Set<Integer> , 依靠数字的范围被限制在 1 到 N 之间，所以使用的空间要少得多(极端情况除外)。