How Can I Efficiently Find Duplicate Integers in a Java Array?

Finding Duplicates in a Java Array

The Problem

You have an integer array and want to efficiently identify any duplicates. Your initial code, attempting to compare each pair of elements, fails to accurately detect duplicates when none exist.

The Issue

The flaw in the code lies in its reliance on the duplicates flag being initialized to false in all cases. If no duplicates are found, the loop will still set duplicates to true when checking the diagonal elements (i.e., when j == k).

A More Nuanced Solution

To remedy this, ensure that the duplicates flag is set to true only when actual duplicates are found. This can be achieved by omitting comparisons of zipcodeList[j] with itself when j == k.

Here's the revised code:

duplicates = false;
for (int j = 0; j < zipcodeList.length; j++) {
    for (int k = 0; k < zipcodeList.length; k++) {
        if (k != j && zipcodeList[k] == zipcodeList[j]) {
            duplicates = true;
        }
    }
}

A Faster Approach

The above solution has a runtime complexity of O(n²), where n is the number of elements in the array. For large arrays, this approach can be inefficient.

A more efficient method to detect duplicates is to leverage a hash-based approach, reducing the time complexity to O(n). Here's an example using a HashSet:

boolean duplicates(int[] zipcodeList) {
    Set<Integer> lump = new HashSet<>();
    for (int zipcode : zipcodeList) {
        if (lump.contains(zipcode)) {
            return true;
        }
        lump.add(zipcode);
    }
    return false;
}

Alternatively, an O(n) solution can be achieved using a boolean[] array (bitmap) to track previously encountered elements and set duplicates to true when an element is encountered a second time.

Conclusion

Depending on the size of the input array and the frequency of duplicates, the choice of approach should be tailored to optimize efficiency.

The above is the detailed content of How Can I Efficiently Find Duplicate Integers in a Java Array?. For more information, please follow other related articles on the PHP Chinese website!