1 Reply Latest reply: Jul 3, 2008 2:51 AM by 843785 RSS

    Finding duplicates in Array

    843785
      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
          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.