从排序数组列表中删除重复项并返回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();

    }

请在编码器链接处测试代码。

https://coderpad.io/MXNFGTJC

Answer 1

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

1. 算法不正确。
2. 该问题与如何从 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)您可以使用and ...实现滑动窗口删除ArrayList::set(int, <E>)，然后重复删除最后一个元素以修剪列表。