与下面的代码相比,是否有更好的方法从数组列表中删除重复项,当遇到更大的输入时,下面的代码在 O(n) 中完成工作。任何建议,将不胜感激。谢谢。
注意:- 不能使用任何额外空间,应就地解决。
输入:- 它将是一个带有重复元素的排序数组。
代码:-
public int removeDuplicates(ArrayList<Integer> a) {
if(a.size()>1){
for( int i=0;i<a.size()-1;i++ ) {
if(a.get(i).intValue() == a.get(i+1).intValue() ) {
a.remove(i);
i--;
}
}
}
return a.size();
}
请在 coder pad 链接上测试代码。
最佳答案
如果此代码用于删除未排序 列表的元素,则:
- 算法不正确。
- 问题与How do I remove repeated elements from ArrayList?重复(例如……)
如果列表是排序的,那么:
- 算法正确。
算法不是
O(N)
.实际上是O(ND)
平均在哪里N
是列表长度,D
是重复的数量。为什么?因为
ArrayList::remove(int)
是平均O(N)
操作!
有两种有效的方法可以从列表中删除大量元素:
创建一个新列表,迭代旧列表并将要保留的元素添加到新列表中。然后丢弃旧列表或清除它并将新列表复制到旧列表。
这对所有标准类型的列表都有效 (O(N))。
执行滑动窗口移除。数组的算法是这样的:
int i = 0; for (int j = 0; j < array.length; j++) { if (should remove array[j]) { // do nothing } else { array[i++] = array[j]; } } // trim array to length i, or assign nulls or something.
如您所见,这执行了一次遍历数组,即
O(N)
.它还避免分配任何临时空间。您可以使用
ArrayList::get(int)
实现滑动窗口移除和ArrayList::set(int, <E>)
...然后重复删除最后一个元素以修剪列表。
关于java - 从排序数组列表中删除重复项并在 java 中返回大小而不使用额外空间,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/49216627/