Java：不使用外部类或方法统计数组中的重复元素数量

Got it, let's tackle this problem head-on. The task is to count how many duplicate elements exist in a double array, and we can only use basic arrays—no HashSet, ArrayList, or other collection classes allowed. Let's walk through a solid approach and code that handles all the edge cases you mentioned.

Core Idea #

Instead of using collections to track unique elements, we can use two auxiliary arrays:

1. One to store the unique elements we've encountered so far.
2. Another to store the count of each unique element.

Once we've traversed the input array and counted occurrences for each unique value, we calculate the total duplicates by summing up (count - 1) for every element (since an element appearing n times contributes n-1 duplicates).

Java Implementation #

Here's a complete method that follows this logic:

public class DuplicateCounter {
    public static int numDuplicates(double[] arr) {
        // Handle edge cases first
        if (arr == null || arr.length <= 1) {
            return 0;
        }

        // Auxiliary arrays: one for unique elements, one for their counts
        double[] uniqueElements = new double[arr.length];
        int[] counts = new int[arr.length];
        int uniqueCount = 0;

        for (double num : arr) {
            boolean found = false;
            // Check if the number is already in our unique elements array
            for (int i = 0; i < uniqueCount; i++) {
                if (uniqueElements[i] == num) {
                    counts[i]++;
                    found = true;
                    break;
                }
            }
            // If not found, add it to the unique array with count 1
            if (!found) {
                uniqueElements[uniqueCount] = num;
                counts[uniqueCount] = 1;
                uniqueCount++;
            }
        }

        // Calculate total duplicates
        int totalDuplicates = 0;
        for (int i = 0; i < uniqueCount; i++) {
            totalDuplicates += counts[i] - 1;
        }

        return totalDuplicates;
    }

    // Test the method with your examples
    public static void main(String[] args) {
        System.out.println(numDuplicates(new double[] {})); // 0
        System.out.println(numDuplicates(new double[] {11.0})); // 0
        System.out.println(numDuplicates(new double[] {11.0, 11.0, 11.0, 11.0})); // 3
        System.out.println(numDuplicates(new double[] {11.0, 11.0, 11.0, 11.0, 22.0, 33.0, 44.0, 44.0, 44.0, 44.0, 44.0, 55.0, 55.0, 66.0, 77.0, 88.0, 88.0})); // 9
    }
}

How It Works #

1. Edge Case Handling: We immediately return 0 for empty arrays or arrays with a single element—since there's no way to have duplicates here.
2. Tracking Unique Elements: As we iterate through the input array, we check if each number is already in our uniqueElements array. If it is, we increment its count. If not, we add it to the array and set its count to 1.
3. Calculating Duplicates: For each unique element, any occurrence beyond the first is a duplicate. Summing counts[i] - 1 gives us the total number of duplicates.

Alternative Approach: Double Loop with Markers #

If you prefer a more memory-efficient approach (though still O(n) space), you can use a boolean array to mark elements we've already counted as duplicates:

public static int numDuplicates(double[] arr) {
    if (arr == null || arr.length <= 1) {
        return 0;
    }

    boolean[] marked = new boolean[arr.length];
    int count = 0;

    for (int i = 0; i < arr.length; i++) {
        if (marked[i]) continue; // Skip elements already marked as duplicates
        for (int j = i + 1; j < arr.length; j++) {
            if (!marked[j] && arr[i] == arr[j]) {
                count++;
                marked[j] = true;
            }
        }
    }

    return count;
}

This works by marking each duplicate element once, so we don't count the same duplicate multiple times during the nested loops.

Testing the Examples #

Both methods will correctly return the expected outputs for your test cases:

• Empty array → 0
• Single element → 0
• Four 11.0s → 3 duplicates (since one is the original, three are copies)
• The longer mixed array → 9 duplicates (3 from 11.0, 4 from 44.0, 1 from 55.0, 1 from 88.0—total 3+4+1+1=9)

内容的提问来源于stack exchange，提问作者DejaEntendouche