arrays - 通过不使用集合来删除具有 O(N) 的重复数组元素？

Question

假设我有一个整数元素数组，在这里我想删除所有重复的元素并打印剩余的元素而不使用任何 Java.util 类。我使用 2 个指针来扫描并删除所有重复项，但需要 O(N^2) 来解决它。我只是想知道是否有任何算法可以在 O(N) 中完成这项任务？

例子：

Input Array:    [1, 2, 3, 4, 5, 4, 3, 4, 6]
Expected Array: [1, 2, 5, 6]

Answer 1

您可以使用存储桶来实现 O(N) + C（使用 HUGE C），但要以存储为代价

1. 创建一个名为 bucket[MAX_INT] 的 MAX_INT 大小的整数数组
2. 循环输入数组。如果值为x，则增加bucket[x]++；
3. 再次循环输入数组。对于每个 x 如果 bucket[x] == 1，添加到预期数组中。

bucket[] 数组可以替换为更好的数据结构。但它仍然达到 O(N)

Answer 2

我会使用一套。

for each item:
  if item is in the Set
    ignore it
  else
    copy it somewhere or output it or whatever
    add it to the Set

那应该对你有用。

使用 aHashSet似乎具有 O(1) 复杂度add和contains（Java 中 set 的时间复杂度）

Answer 3

您可以使用任何算法对所有元素进行排序，例如合并排序、复杂度为 n lg n 的快速排序。然后使用堆栈向其中添加元素。继续将元素推入堆栈，直到找到重复项。如果重复元素从堆栈中弹出，它将删除重复元素。总复杂度为 O(n lg n)。这可能是解决问题的有效方法。