CODEWITHSUNDEEP
javaarrayslistlinked-list
z atef
z atef

Reputation: 7689

find duplicates in a sorted linkedlist in O(n) time

What is the most efficient way do this? Is using iterator ok?

public class FindDuplicates {
    public static void main(String arg[]){
        int[] str={1 , 2 , 3 ,4  ,5 ,3 ,5 , 4,3,43,1,33,4,5};
        List<Integer> list = new LinkedList<Integer>();

        for(int x : str) {   
            list.add(x);    
        }

        Collections.sort(list);
        System.out.println(list);

        Iterator<Integer> it = list.listIterator();  
        while(it.hasNext() && it.next() != null) { 
            /*   Pseudocode =>   if(it.next().equals(it.next.next)); */
            /* OR Pseudocode =>  if(it.next() == it.next().next) */ 
            System.out.println(it) ;
        }
    }
}

Upvotes: 0

Views: 5199

Answers (5)

Prateek
Prateek

Reputation: 1926

A better way of doing it would be . Instead of Collections.sort which is above O(N) complexity use a Hash Set unless you have a constraint on the space complexity. A basic pseudo code would be something like.

  if(set.contains(it)){// Check if it.info is in map or not
    System.out.println(it.info); // If it was then it is duplicate element hence print it
    }
  else{
    set.put(it);// Else if this is the first time you saw this element put it in set.
    }

This code has O(N) time complexity.

Upvotes: 1

sebtic
sebtic

Reputation: 198

All the forms with array, with list, with linked list.

import java.util.Arrays;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

public class Main {

    public static void withArray() {
        int[] str = { 1, 2, 3, 4, 5, 3, 5, 4, 3, 43, 1, 33, 4, 5 };
        Arrays.sort(str);

        int previous = str[0];
        for (int i = 1; i < str.length; ++i) {
            if (str[i] == previous) {
                System.out.println("Duplicate " + previous + " and " + str[i]);
            }
            previous = str[i];
        }
        System.out.println();
    }

    public static void withList() {
        List<Integer> str = Arrays.asList(1, 2, 3, 4, 5, 3, 5, 4, 3, 43, 1, 33,
                4, 5);
        Collections.sort(str);

        int previous = str.get(0);
        for (int i = 1; i < str.size(); ++i) {
            if (str.get(i) == previous) {
                System.out.println("Duplicate " + previous + " and "
                        + str.get(i));
            }
            previous = str.get(i);
        }
        System.out.println();
    }

    public static void withLinkedList() {
        LinkedList<Integer> str = new LinkedList<Integer>(Arrays.asList(1, 2,
                3, 4, 5, 3, 5, 4, 3, 43, 1, 33, 4, 5));
        Collections.sort(str);

        Iterator<Integer> it = str.iterator();

        int previous = it.next();
        int cur;
        while (it.hasNext()) {
            cur = it.next();
            if (cur == previous) {
                System.out.println("Duplicate " + previous + " and " + cur);
            }
            previous = cur;
        }
        System.out.println();
    }

    public static void main(String arg[]) {
        withArray();
        withList();
        withLinkedList();

    }
}

Upvotes: 0

Stefan Haustein
Stefan Haustein

Reputation: 18803

You need to keep the previous value in a variable, should look similar to this:

 Iterator<Integer> it = list.listIterator(); 
 if (it.hasNext()) {
   Integer previous = it.next();
   while(it.hasNext()) { 
     Integer current = it.next();
     if (previous.equals(current)) {
       System.out.println("Dupe: " + current);
     }
     previous = current;
   }
 }

Note that you don't really need a linked list here (as others have pointed out already), you can just sort in place and then scan the array with a single loop:

int[] str={1 , 2 , 3 ,4  ,5 ,3 ,5 , 4,3,43,1,33,4,5};
Arrays.sort(str);
for (int i = 1; i < str.length; i++) {
  if (str[i] == str[i - 1]) {
    System.out.println("Dupe: " + str[i];
  }
}

If you don't want to change str, just keep track of the elements in a HashSet:

int[] str={1 , 2 , 3 ,4  ,5 ,3 ,5 , 4,3,43,1,33,4,5};
HashSet<Integer> seen = new HashSet<Integer>();
for (int i: str) {
  if (seen.contains(i)) {
    System.out.println("Dupe: " + i);
  } else {
    seen.add(i);
  }
}

If you consider the hashtable operations O(1), this also gives you linear time instead of O(n log n)

Upvotes: 5

Sage
Sage

Reputation: 15418

int[] str={1 , 2 , 3 ,4  ,5 ,3 ,5 , 4,3,43,1,33,4,5};

you don't need to use LinkedList just to sort for finding duplicates. use Arrays.sort(int[]) to sort your array and then scan: The following program will print the integer which has duplicates along with duplicates count:

int a[] = {1, 1, 1, 5, 5, 4, 4, 3, 3};

        Arrays.sort(a);

        for(int i=1 ; i<a.length;)
        {
            if(a[i] == a[i-1])
            {
                int j = i;
                for(; j<a.length; j++)
                    if(a[j]!=a[i])break;

                if(j > i)
                    System.out.println("Found duplicate: "+a[i]+" counted: "+(j - i+1));

                i = j;
            }
            else i++;

        }

sample output:

Found duplicate: 1 counted: 3
Found duplicate: 3 counted: 2
Found duplicate: 4 counted: 2
Found duplicate: 5 counted: 2

Upvotes: 0

remram
remram

Reputation: 5202

First of all, note that you are using Collections.sort, which is above O(n) complexity.

About your question: finding duplicates in a sorted list with O(n) complexity:

You can just have one variable that you set to the previous value you encountered, that way in the loop, you just compare the current value with that variable, then set the variable to the current value.

Upvotes: 2

Related Questions