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

Question

最有效的方法是什么？使用迭代器可以吗？

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)