在O(n)时间内在已排序的链表中查找重复项

Question

对于这个问题,我编写了一个代码,在数组中找到重复项并将其打印出来.最初,我使用了时间复杂度为0(n ^ 2)的嵌套循环.为了更高效的0(n)解决方案,我编写了下面的代码,并希望得到一些帮助/见解如何找出是否有任何元素及其.Next()保持相同的值"Duplicates",如果是这样,打印它们出.

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) ;
        }
    }
}

Answer 1

您需要将先前的值保留在变量中,应该类似于:

 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;
   }
 }

请注意,这里并不需要链接列表(正如其他人已经指出的那样),您可以在适当的位置进行排序,然后使用单个循环扫描数组:

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];
  }
}

如果您不想更改str,只需跟踪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);
  }
}

如果考虑哈希表操作O(1),这也会给出线性时间而不是O(n log n)