Java - count duplicates in array without using outside classes or methods?

Question

I need to count the number of dupes in an array, but I'm constrained to only using arrays, no HashSets or ArrayLists.

Here are example inputs with their expected outputs:

numDuplicates(new double[] { }) --> 0
numDuplicates(new double[] { 11.0 }) --> 0
numDuplicates(new double[] { 11.0, 11.0, 11.0, 11.0 }) --> 3
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
numDuplicates(new double[] { 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 }) --> 5

This is the code I have, but it counts duplicates after each number, returning an inflated count, i.e. {11.0, 11.0, 11.0, 11.0} returns 6 instead of 3:

public static int numDuplicates (double[] list) {

    int dupCount = 0;
    for (int i = 0; i < list.length; i++) {
        for (int j = i + 1; j < list.length; j++) {
            if (list[i] == list[j]) {
                dupCount++;
            }
        }
    }

    return dupCount; //TODO1: fix this
}

Note: I'm new on Stack, I tried searching thoroughly but couldn't find an array duplicate question that had similar input/output to mine, but I'm sorry if someone has already asked this.

Based on the example you gave, it looks like you are supposed to find the longest duplicate not just count all the duplicates — smac89, Apr 21 '18 at 23:05
Perhaps this may answer your question: https://stackoverflow.com/a/31738825/9488265 — J Duh, Apr 21 '18 at 23:07
No actually it looks like you're right ignore previous comment — smac89, Apr 21 '18 at 23:07
All you need to do to fix your code is insert a `break;` after you increment `dupCount`. That way you only count each duplicate once. — 4castle, Apr 21 '18 at 23:08
Are the duplicates always consecutive? Should `new double[] { 1, 2, 1 }` return 0 or 1? — 4castle, Apr 22 '18 at 16:36

smac89 · Accepted Answer · 2018-04-22T23:39:53.540

1

Simple fix:

public static int numDuplicates (double[] list) {

    int dupCount = 0;
    for (int i = 0; i < list.length; i++) {
        for (int j = i + 1; j < list.length; j++, i++) { // HERE it is
            if (list[i] == list[j]) {
                dupCount++;
            }
        }
    }

    return dupCount;
}

What I did was to increment i in addition to j. What this did was to start i at the place where j stopped. The reason I thought to do that was because you said it was returning an inflated count, so I figured it must be because you are doing too many counts and that was exactly what was happening.

i was always following in increments of 1 rather than increments of the size of the last duplicate counts found, so it was always repeating counts.

As to how the j++, i++ works - it is just a series of expressions. Java allows you to separate expressions that evaluate to the same type, using a comma.

As per the comments, you can remove the outer loop:

public static int numDuplicates (double[] list) {

    int dupCount = 0;
    for (int i = 1; i < list.length; i++) {
        if (list[i] == list[i - 1]) {
            dupCount++;
        }
    }
    return dupCount;
}

edited Apr 22 '18 at 23:39

answered Apr 21 '18 at 23:11

smac89

39,374
15
132
179

Wow, I never knew you could do this! But how does j++, i++ work? – Raymo111 Apr 21 '18 at 23:14
That worked! I'm new to Java, would you mind explaining what that changed functionally? – DejaEntendouche Apr 21 '18 at 23:17
Explanation coming guys, hang tight – smac89 Apr 21 '18 at 23:19
If you increment `i` and `j` at the same time, they will always be adjacent indexes. You might as well remove the outer loop and calculate `i` as `j - 1`. – 4castle Apr 22 '18 at 16:32
@4castle, noted – smac89 Apr 22 '18 at 23:40

score 0 · Answer 2 · answered Apr 21 '18 at 23:14

0

You could use another array like so:

public static int numDuplicates(double[] list) {

    double[] duparray = new double[list.length];
    int dupCount = 0;
    for (int i = 0; i < list.length; i++) {
        for (int j = i + 1; j < list.length; j++) {
            if (list[i] == list[j] && !(list[i] == duparray[i])) {
                duparray[i] = list[i];
                dupCount++;
            }
        }
    }

    return dupCount;
}

answered Apr 21 '18 at 23:14

Raymo111

514
8
24

This won't work if the input array contains any zeros. A better solution would be to use a `boolean[]` array instead that indicates if the value at that index has already been counted as a duplicate. – 4castle Apr 22 '18 at 16:41
If the input array was `new double[]{ 0, 0 }` for example, it would already count the values as equal to the default values in `dupArray`, so it would return `0` duplicates instead of `1`. – 4castle Apr 22 '18 at 17:03

Java - count duplicates in array without using outside classes or methods?

2 Answers2