java - 如何修改我的方法以在 O(N) 或 O(N * log N) 中搜索然后删除重复项？

Question

我创建了一个方法来搜索重复项，然后将重复项索引存储到另一个数组中。然后我遍历我的大数组并移动所有条目而不重复。

现在，我的问题是这使用了 O(N*N) 并且我正在使用额外的内存空间，因为我正在添加额外的数组。

这怎么可能？ 假设我需要了解如何在不使用其他库或 HashSet 的情况下完成此操作。

感谢任何提示。

   public void dups()
   {
       int[] index = new int[100];

       int k = 0;
       int n = 0;
       int p = 0;

       for (int i = 0; i < elements; i++)
           for (int j = i + 1; j < elements; j++)
               if(a[j].equals(a[i]))
                   index[k++] = i;

       for (int m = 0; m < elements; m++)
           if (m != index[p])
               a[n++] = (T) a[m];
           else
               p++;

       elements -= k;
   }

Answer 1

您无法在 O(n) 中找到重复项(通常)。

但是在 O(n*log n) 中是可能的。只需对数组进行排序 (O(n*log n))，然后可以在 O(n) 中扫描重复项。

另一方面，如果您可以使用哈希表(如果您不想使用任何额外的库，您可能不想这样做)，您可以扫描数组并计算每个元素出现的频率在数组中。之后，您可以遍历哈希表中的每个元素，找到那些出现不止一次的元素。这将花费 O(n) 的预期 运行时间，但不是确定性的 O(n)。

最后，为什么我写的是一般在 O(n) 中找不到重复项？
可以想象几种特殊情况，其中可以在 O(n) 中找到重复项。 例如，您的数组只能包含 0 到 99 之间的数字。 在这种情况下，您可以使用另一个数组(大小为 100)来计算每个元素在数组中出现的频率。这与哈希表的工作方式相同，但它的运行时间是确定性的 O(n)。

另一个可以在 O(n) 中找到重复项的示例当然是，如果数组已经排序。