2

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

第一个是对整数数组进行排序并进行比较。第二个只是使用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;
    }
}

哪一个更好？有没有更好的解决方案？

4

2 回答 2

5

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

于 2013-10-13T03:18:40.110 回答
1

哈希集实现更节省时间，但数组排序实现在内存使用方面更有效。

时间：向散列集添加值具有恒定的复杂度，O(1) - 散列集有多大并不重要。然而，arrayCopy 具有线性复杂度，O(n)。此外，根据您对数组进行排序的方式，这也需要一些时间。

内存：您的数组实现仅使用原始数组的两倍内存。您的哈希集可能会比原始数组大得多。

于 2013-10-13T03:26:04.107 回答