java - 从排序数组列表中删除重复项并在 java 中返回大小而不使用额外空间

Question

与下面的代码相比，是否有更好的方法从数组列表中删除重复项，当遇到更大的输入时，下面的代码在 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 链接上测试代码。

https://coderpad.io/MXNFGTJC

Answer 1

如果此代码用于删除未排序 列表的元素，则:

1. 算法不正确。
2. 问题与How do I remove repeated elements from ArrayList?重复(例如……)

如果列表是排序的，那么:

1. 算法正确。

2. 算法不是 O(N) .实际上是O(ND)平均在哪里 N是列表长度，D是重复的数量。

   为什么？因为ArrayList::remove(int)是平均 O(N)操作!

有两种有效的方法可以从列表中删除大量元素:

1. 创建一个新列表，迭代旧列表并将要保留的元素添加到新列表中。然后丢弃旧列表或清除它并将新列表复制到旧列表。

   这对所有标准类型的列表都有效 (O(N))。

2. 执行滑动窗口移除。数组的算法是这样的:

       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>) ...然后重复删除最后一个元素以修剪列表。