Search code examples
javaalgorithmpseudocodeseries

pseudo code to find the numbers which appear more than once in a list

I have a series like 1,2,199,100,8,100,199,1001,5,9 and I got to write a pseudo code to find out the numbers which appear more then once in the above list. I can clearly see that 199 and 100 appear twice in the list and that should be the answer but how should I write the pseudocode for it? My logic is something like this:

   array x = {1,2,199,100,8,100,199,1001,5,9}
   array y
   array j
for(int i = 0;i< 9; i++){
 if x[i] exists in y
     j[i] = y
 else
    y[i] = x


}
Solution

  • Sort the list with quick sort or merge sort (n log n) then do a single pass over the list comparing the current number to the previous O(n). If the previous number equals the current then you have a duplicate.

    EDIT:

    Array array = {1,2,199,100,8,100,199,1001,5,9}
Array sorted = sort(array)
for (int i=1; i<sorted.length; i++)
    int p = sorted[i-1]
    int c = sorted[i]
    if (p==c) print "duplicate"