java - 如何在数组中找到两个重复元素

Question

下面的代码工作正常，但复杂度为 O(n^2)。是否可以在 O(n) 或 O(log n) 时间内完成。

public class TwoRepeatingElements {
    public static void main(String[] args) {
        Integer array[] = {4, 2, 4, 5, 2, 3, 1, 2};
        findTwoRepeatingElements(array);


    }

    private static void findTwoRepeatingElements(Integer[] array) {
        int i, j;
        for(i = 0; i < array.length-1; i++) {
            for(j = i+1; j < array.length-1; j++) {
                if(array[i] == array[j]) {
                    System.out.println(array[i]);
                }
            }
        }

    }

}

Answer 1

显然你不能在小于 O(n) 的时间内找到它，因为你需要扫描整个数组。 您可以将 hastable 用于 O(n) 解决方案。

只需将您的元素插入到一个 hastable 中，当您要插入的元素已经存在时停止。

private static void findTwoRepeatingElements(Integer[] array) {
    Set<Integer> set = new HashSet<Integer>();
    for(int a : array) {
        if(!set.add(a)) {
            System.out.println(a);
            break;
        }
    }
}