java - 哪种查找重复整数的方法更有效？

Question

通常情况下，同一个问题有不同的解决方案。我的是找到重复的整数。我有两种方法。

第一个是对整数数组进行排序并进行比较。第二个是使用 HashSet。你能告诉我哪个更有效率吗？为什么？请注意，原始数组不得被覆盖。

主类

public class Main {
    static DuplicateNumbers dn;
    static DuplicateNumbersHash dnh;

    public static void main(String[] args) {
        int[] arrayOfIntegers = {9, 7, 1, 3, 4, 2, 7, 5, 9};

        // 1st class test
        dn = new DuplicateNumbers(arrayOfIntegers);
        dn.searchForDuplicates();

        System.out.println("\n\n2nd test\n\n");

        // 2nd class test
        dnh = new DuplicateNumbersHash(arrayOfIntegers);
        dnh.searchForDuplicates();

    }
} // Main class

非 HashSet 方法

public class DuplicateNumbers {
    protected int[] arrayOfIntegers;

    public DuplicateNumbers(int[] arrayOfIntegers) {
        this.arrayOfIntegers = arrayOfIntegers;
    }

    public void searchForDuplicates() {
        // do not overwrite original array, so create a temp one instead
        int[] tempArray = new int[arrayOfIntegers.length];
        System.arraycopy(arrayOfIntegers, 0, tempArray, 0,
        arrayOfIntegers.length);

        // sorting temp array only
        Arrays.sort(tempArray);

        // now look for duplicates
        for (int i = 0; i < tempArray.length - 1; i++) {
            if (tempArray[i] == tempArray[i + 1]) {
                System.out.printf(
                    "Duplicates: tempArray[%d] and tempArray[%d]\n", i,
                    i + 1);
                System.out.printf("Repeated value: %d %d\n", tempArray[i],
                    tempArray[i + 1]);
                System.out.println();
            } // if
        } // for
    } // searchForDuplicates()
} // DuplicateNumbers class

HashSet 方法；继承前一个类在这里粘贴更少的代码

public class DuplicateNumbersHash extends DuplicateNumbers {
    public DuplicateNumbersHash(int[] arrayOfIntegers)  {
        super(arrayOfIntegers);
    }

    @Override
    public void searchForDuplicates() {
        Set<Integer> s = new HashSet<Integer>();

        for (int i = 0; i < arrayOfIntegers.length; i++) {
                if (!s.add(arrayOfIntegers[i])) {
                    System.out.printf("Repeated value: %d\n", arrayOfIntegers[i]);
            }
        }

        s = null;
    }
}

哪个更好？还有更好的解决方案吗？

Answer 1

最佳排序算法的时间复杂度是O(n log n)，所以排序方法也是O(n logn)。 HashSet 方法的复杂度为 O(n)。因此，理想情况下，您应该使用 HashSet 方法。