CODEWITHSUNDEEP
algorithm
Elton.fd
Elton.fd

Reputation: 1595

Algorithm to find duplicate in an array

I have an assignment to create an algorithm to find duplicates in an array which includes number values. but it has not said which kind of numbers, integers or floats. I have written the following pseudocode:

 FindingDuplicateAlgorithm(A) // A is the array
      mergeSort(A);
      for  int i <- 0 to i<A.length
           if A[i] == A[i+1]
                 i++
               return  A[i]
           else
                 i++

have I created an efficient algorithm? I think there is a problem in my algorithm, it returns duplicate numbers several time. for example if array include 2 in two for two indexes i will have ...2, 2,... in the output. how can i change it to return each duplicat only one time? I think it is a good algorithm for integers, but does it work good for float numbers too?

Upvotes: 11

Views: 51385

Answers (6)

smaiakov
smaiakov

Reputation: 480

 public void printDuplicates(int[] inputArray) {
    if (inputArray == null) {
        throw new IllegalArgumentException("Input array can not be null");
    }
    int length = inputArray.length;

    if (length == 1) {
        System.out.print(inputArray[0] + " ");
        return;
    }

    for (int i = 0; i < length; i++) {

        if (inputArray[Math.abs(inputArray[i])] >= 0) {
            inputArray[Math.abs(inputArray[i])] = -inputArray[Math.abs(inputArray[i])];
        } else {
            System.out.print(Math.abs(inputArray[i]) + " ");
        }
    }
}

Upvotes: 0

Maksood
Maksood

Reputation: 1200

O(n) algorithm: traverse the array and try to input each element in a hashtable/set with number as the hash key. if you cannot enter, than that's a duplicate.

Upvotes: 1

Bj&#246;rn Pollex
Bj&#246;rn Pollex

Reputation: 76876

To handle duplicates, you can do the following:

if A[i] == A[i+1]:
    result.append(A[i]) # collect found duplicates in a list
    while A[i] == A[i+1]: # skip the entire range of duplicates 
        i++               # until a new value is found

Upvotes: 13

Christian Kuetbach
Christian Kuetbach

Reputation: 16060

Do you want to find Duplicates in Java?

You may use a HashSet.

HashSet h = new HashSet();
for(Object a:A){
   boolean b = h.add(a);
   boolean duplicate = !b;
   if(duplicate)
       // do something with a;
}

The return-Value of add() is defined as:

true if the set did not already contain the specified element.

EDIT: I know HashSet is optimized for inserts and contains operations. But I'm not sure if its fast enough for your concerns.

EDIT2: I've seen you recently added the homework-tag. I would not prefer my answer if itf homework, because it may be to "high-level" for an allgorithm-lesson

http://download.oracle.com/javase/1.4.2/docs/api/java/util/HashSet.html#add%28java.lang.Object%29

Upvotes: 11

Nico Huysamen
Nico Huysamen

Reputation: 10427

Your answer seems pretty good. First sorting and them simply checking neighboring values gives you O(n log(n)) complexity which is quite efficient.

Merge sort is O(n log(n)) while checking neighboring values is simply O(n).

One thing though (as mentioned in one of the comments) you are going to get a stack overflow (lol) with your pseudocode. The inner loop should be (in Java):

for (int i = 0; i < array.length - 1; i++) {
    ...
}

Then also, if you actually want to display which numbers (and or indexes) are the duplicates, you will need to store them in a separate list.

Upvotes: 2

Niki
Niki

Reputation: 15867

Your algorithm contains a buffer overrun. i starts with 0, so I assume the indexes into array A are zero-based, i.e. the first element is A[0], the last is A[A.length-1]. Now i counts up to A.length-1, and in the loop body accesses A[i+1], which is out of the array for the last iteration. Or, simply put: If you're comparing each element with the next element, you can only do length-1 comparisons.

If you only want to report duplicates once, I'd use a bool variable firstDuplicate, that's set to false when you find a duplicate and true when the number is different from the next. Then you'd only report the first duplicate by only reporting the duplicate numbers if firstDuplicate is true.

Upvotes: 0

Related Questions