CODEWITHSUNDEEP
javaarraysmethods
Memorial_Trash
Memorial_Trash

Reputation: 13

Find the distinct duplicates in an array

I'm trying to write a method to find duplicate values within an array, and return true when that happens twice (otherwise returning false).

I have something, but for some reason, it doesn't work properly under a certain case:

public static boolean twoDuplicates(int[] values) {

    boolean twoDuplicate = false;
    int counter = 0;

    for(int i = 0; i < values.length; i++){
        for(int z = i + 1; z <= values.length - 1; z++){
            if(i != z && values[i] == values[z])
                counter++;
        }
    }
    if(counter == 2)
        twoDuplicate = true;
    return twoDuplicate;
}

Now, I tested it out, and it doesn't work when the values are [3,3,3,6,6]. Is there a reason why?

EDIT: I forgot to mention that the duplicates HAVE to be distinct.

Upvotes: 0

Views: 900

Answers (6)

edymerchk
edymerchk

Reputation: 1263

this is how I would do it with just one loop

    public static boolean twoDuplicates(int[] values) {
    HashSet<Integer> map = new HashSet<Integer>();
    int cont = 0;
    for (int i = 0; i < values.length; i++) {
        if (map.contains(values[i])){
            cont++;
            if (cont == 2) 
                return true;
        }           
        else
            map.add(values[i]);

    }
    return false;
}

Upvotes: 0

Vitaly
Vitaly

Reputation: 2800

1 . You need to remember the value of the first duplicate pair found.

Otherwise, in a row 3,3,3 - you will find 3 two times. So store the first duplication value and compare this is not it.

int firstDuplicate;


if(i != z && values[i] == values[z]) {

     if (counter == 0) {

          counter++;
          firstDuplicate = values[i];

     } else if (counter == 1 && values[i] != firstDuplicate) {

          counter++;
     }
}

2 . z <= values.length - 1 should be z < values.length. As you used in the first for.

3 . Always use { } even if the block is single-lined.

UPD

4 . Use break; to stop iterating when you found what you need.

for(){
    for(){

    }
    if(counter == 2) {
        twoDuplicate = true;
        break;
    }
}

Or better 

for(int i = 0; i < values.length && counter < 2; i++;){
    for(){

    }
}

return counter >= 2;

Upvotes: 0

Tomasz
Tomasz

Reputation: 415

In your existing code you are counting the number of pairs rather than finding duplicates. You should check counter separately for each 'i'.

public static boolean twoDuplicates(int[] values) {

boolean twoDuplicate = false;

for(int i = 0; i < values.length; i++){
int counter = 0;
for(int z = i + 1; z <= values.length - 1; z++){
        if(i != z && values[i] == values[z])
            counter++;
    }
   if(counter == 2) // or if(counter > 1) if finding three duplicates is also fine
      return true;
}

return false;
}

Or 

public static boolean twoDuplicates(int[] values) 
{
    for(int i = 0; i < values.length; i++)
    {
       int counter = 0;
       for(int z = i + 1; z <= values.length - 1; z++)
       {
            if(values[i] == values[z])
            {
                counter++;
                if(counter == 2) // check here if you want 2 or more duplicates
                   return true;
            }
        }
        // check here if you want exactly two duplicates
    }

    return false;
}

Upvotes: 1

munch1324
munch1324

Reputation: 1148

It looks like you are just counting the total number of matches. ie you will be matching 3 twice (counter = 3 now) and z once for a total of 4. When I run this code with the array I get counter = 4;

I think the following code will return the number of distinct duplicates (number with a duplicate, no matter how many times it occurs). This will return 2 for the test array. It first sorts the array, then finds duplicates, ignoring duplicates that have already been counted. 

public static boolean twoDuplicates(int[] values) {

        boolean twoDuplicate = false;
        int counter = 0;
        Arrays.sort(values);
        int old = values[0];
        boolean numberSeen = false;
        for(int i = 0; i < values.length; i++){
            if(values[i] == old){
                if(!numberSeen){
                    counter++;
                    numberSeen = true;
                }
            }else{
                numberSeen = false;
                old = values[i];
            }
        }
        if(counter == 2)
            twoDuplicate = true;
        return twoDuplicate;
    }

Upvotes: 1

tcak
tcak

Reputation: 2212

Situation is like that:

First loop reads first 3. Second loop reads second and third 3s. Counter becomes 2. First loop reads second 3. Second loop reads third 3. Counter becomes 3. First loop reads third 3. Second loop cannot find anything. Counter is 3. First loop reads first 6. Second loop reads second 6. Counter is 4. First loop reads second 6. Second loop cannot find anything. Counter is 4.

What you need to do is to put that if( counter == 2 ) after second loop. This will solve your problem.

if( counter == 2 ) return true;

Upvotes: 0

sayume
sayume

Reputation: 128

According to your logic, if you have more than 2 duplicates,the function will return false, maybe you should use "counter>1" for judge, and the counter definition should be placed in the outer iteration. And I think the algorithm is not clever enough.

Upvotes: 0

Related Questions