最有效的方法是什么?使用迭代器可以吗?
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) ;
}
}
}
最佳答案
您需要将先前的值保留在变量中,应类似于以下内容:
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)
关于java - 在 O(n) 时间内查找排序链表中的重复项,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19894957/