searching for duplicates in an array

Question

If I initialise an array of person objects with this data

myPeople[0] = new Person("Alice", "Foo", 22 );
myPeople[1] = new Person("Alice", "Foo", 22 );
myPeople[2] = new Person("Bob", "Bar", 2);
myPeople[3] = new Person("Joe", "Blogs", 64);
myPeople[4] = new Person("Jane", "Joe", 42);

I want to my method to return the number of duplicates. In this case it would be 2, as Person 0 and 1 are dublicates of each other. If I were to change object 2 to be the same it should return 3. At the moment my method returns 1 wth two duplicates and 4 with three.

The method in question:

public static int searchForClones(Person[] array){
    int numberOfClones=0;
    for(int j =0; j<array.length-1; j++)
    {
        String tmp1 = array[j].getFirstName();          //Store first element of the array in tmp so it can be compared
        String tmp3 = array[j].getLastName();   
        for(int i = 0; i<array.length-1; i++)           //Loop to compare for every element in the array
        {   
            String tmp2 = array[i].getFirstName();      //Do the same for the next element
            String tmp4 = array[i].getLastName();
            if(i!=j)                                    //If i an j aren't the same element
            {

                if(tmp1.equals(tmp2) && tmp3.equals(tmp4)   //and if they match
                    && array[i].getAge()==array[i+1].getAge())
                {   
                    numberOfClones++;                   //increment the number of clones
                }
           }
       }
    }
    return numberOfClones;
}

I'd really appreciate any help, as I think the only problem is the way I increment the number of clones. Maybe I need to check something and increment by an appropriate number after that?

In your example there is only one duplicate, why should it return 2? — Bhesh Gurung, Feb 25 '13 at 04:11
In my example it could be argued that there is only one duplicate and another is an original, but for what I'm doing I'm calling them duplicates of each other. — oneshotfinch, Feb 25 '13 at 04:20

score 3 · Answer 1 · answered Feb 25 '13 at 04:04

3

Heres one way:

public static int searchForClones(Person[] array){
    if(array == null || array.length == 0) return 0;

    return array.length - new HashSet(Arrays.asList(array)).size();
}

As always, make sure to implement to implement the equals and hashCode method of your Person object, properly.

answered Feb 25 '13 at 04:04

Perception

79,279
19
185
195

1

Are you sure OP implemented `hashCode()` and `equals()` correctly in Person class? – Pshemo Feb 25 '13 at 04:05
@Pshemo - Fair enough, note added. – Perception Feb 25 '13 at 04:07
This is going to return 1. – Bhesh Gurung Feb 25 '13 at 04:07

Pshemo · Answer 2 · 2013-02-25T04:55:12.750

Your second for should start from j+1 or you will compare same pair of elements two times for example once when j=0 and i=1, second when j=1 and i=0.
Change condition of second for loop to i<array.length or you will skip last element
Change
```
array[i].getAge()==array[i+1].getAge()
```
to
```
array[i].getAge()==array[j].getAge()
```
because you want to compare elements from first iteration with elements from second iteration, not "neighbor" elements.

Also remember that this method will return number of pair of identical element, not number of identical elements.

To count number of identical elements you should probably sort your array earlier so that identical elements would be near each other, then iterate over that array and for every firs pair of X element increase counter by 2 (since there are two identical elements), for every next pair of X elements increase counter by 1 (there is only one new element now).

This seems to be on the right track, however when I implemented the change it returned only 1 for when objects 0 and 1 both matched. When I matched 3 objects it returned 3, and also returned 3 if I matched 4 or 5 objects. — oneshotfinch, Feb 25 '13 at 04:25

score 0 · Answer 3 · answered Feb 25 '13 at 04:34

public static int searchForClones(Person[] array)
{
    int numberOfClones = 0;
    for(int i=0; i<array.length-1; i++)
    {
        for(int j=i+1; j<array.length; j++)
        {
            if(array[i].getFirstName().equals(array[j].getFirstName())
                && array[i].getLastName().equals(array[j].getLastName())
                && array[i].getAge() == array[j].getAge()) )
            {
                numberOfClones++;
            }
        }
    }

    return numberOfClones > 0 ? ++numberOfClones : 0;  // To count the one which was duplicate of itself (as per your comment)
}

With the above program
Input:

myPeople[0] = new Person("Alice", "Foo", 22 );
myPeople[1] = new Person("Alice", "Foo", 22 );
myPeople[2] = new Person("Bob", "Bar", 2);
myPeople[3] = new Person("Joe", "Blogs", 64);
myPeople[4] = new Person("Jane", "Joe", 42);

Output: 2

But what if the input is:

myPeople[0] = new Person("Alice", "Foo", 22 );
myPeople[1] = new Person("Alice", "Foo", 22 );
myPeople[2] = new Person("Bob", "Bar", 2);
myPeople[3] = new Person("Joe", "Blogs", 64);
myPeople[3] = new Person("Joe", "Blogs", 64);

How do you expect the count as????

searching for duplicates in an array

3 Answers3