This discussion is archived
1 Reply Latest reply: Jul 3, 2008 12:51 AM by 843785 RSS

Finding duplicates in Array

843785 Newbie
Currently Being Moderated
Hi Friends,
I would like to know what should be the approach to solve questions like these:

1. In an array of X elements, check to see if there are any duplicate values by providing 2 approachs:

a. to maximize-performance (0(n))
b. to minimize-memory-usage

I wrote this test program to find duplicates and now I wonder how can i change my program to follow the above said 2 approaches:
import java.util.*;
public class test{
     public static void main(String[] ar)
     {
     int[] arr = {3,5,6,4,2,3,5,2,4,2};
     StringBuffer sb = new StringBuffer();

     Arrays.sort(arr);
     boolean flag=false;

     for(int i=0;i<10;i++)
     {
          System.out.println(arr);
     }

     for(int i=0;i<9;i++)
     {
               if(arr[i]==arr[i+1]){
                    if(!flag)
                         sb.append(arr[i]+" ");
                    flag=true;                    
                    continue;
               }else{          
                    flag=false;
               }
     }
     System.out.println("Duplicates:"+sb.toString());
}
}


Your help would be greatly appreciated. Thanks in advance.
  • 1. Re: Finding duplicates in Array
    843785 Newbie
    Currently Being Moderated
    java80 wrote:
    I wrote this test program to find duplicates and now I wonder how can i change my program to follow the above said 2 approaches:
    You already have achieved b. The integers must be stored somewhere and you don't use any additional storage. The naive approach gives an O(N*N) algoritm but by first sorting you've changed that to an O(N*logN) algoritm which is better

    To achieve a. you need to add a data structure namely a set. The algoritm goes,

    For all integers in the array {
    If the integer is in the set it's a duplicate.
    Add the integer to the set.
    }

    For the set you can use a HashSet or implement your own set using an integer array. It's important that you can check whether an integer is in the set in O(1) time.

    Thanks to the set's O(1) behavior the above algoritm will be O(N) and that's the fastest possible. The cost is the set you need.