Java 中从数组中删除重复项

在 Java 中，有几种方法可以从数组中删除重复项，每种方法都满足特定需求。我们将探索诸如使用集合（或 HashSet）、原地对数组进行排序以及使用映射或频率数组等方法。

1. 使用集合（或 HashSet）

使用 HashSet 可以灵活地处理重复项，特别是当值的范围较宽或未知时。

要存储我们已经看到的元素，请创建一个 HashSet。数组元素将用作键，值可以是整数计数或布尔值。

• 检查每个元素是否是 HashMap 中的键。
• 如果不存在，请将其添加到 HashMap 并继续。
• 如果它已经存在，我们就找到了一个重复项。之后，我们可以将首选的替换值替换原始数组中的此元素。
• 此方法具有平均时间复杂度 O(n)，非常灵活。

输出

Original Array: [22, 33, 44, 22, 33, 66, 11, 88, 44]
After removing duplicates: [33, 66, 22, 88, 11, 44]

复杂度分析

时间复杂度

为了将元素添加到 HashSet，代码会迭代输入数组一次。添加到 HashSet 的平均时间是常数。然后通过迭代 HashSet 来复制唯一元素。元素数量“n”决定了这两个循环的比例。因此，总时间复杂度为 O(n)。

空间复杂度

代码通过在 HashSet 中存储唯一元素后返回结果，使用新数组。在最坏的情况下，每个组件都是不同的。因此，HashSet 将存储 n 个元素，新数组的大小也将是 n。由于内存使用量与输入的大小成线性关系，因此空间复杂度为 O(n)。

2. 原地对数组进行排序

此方法非常适合我们无法使用额外内存的情况。通过先对数组进行排序，所有重复的元素都会彼此相邻，从而可以轻松识别和覆盖它们。

输出

Sorted array: [11, 22, 33, 44, 66, 88, 44, 66, 88]
After remove duplicates: [11, 22, 33, 44, 66, 88]

复杂度分析

时间复杂度

Arrays.sort(arr) 调用是影响时间复杂度的主要因素。对于原始类型，Java 的 Arrays.sort() 方法使用双枢轴快速排序算法，该算法的平均和最坏情况时间复杂度为 O(n log n)。之后用于查找唯一元素的循环以线性时间 O(n) 执行。由于排序步骤耗时最长，总时间复杂度为 O(n log n)。

空间复杂度

由于代码在原地操作原始数组，因此空间复杂度为 O(1)。对于原始类型，Arrays.sort() 方法不需要大量额外空间。循环中使用固定数量的变量（i 和 j）。最后一个 Arrays.copyOf() 调用创建了一个新数组，但这只是为了返回结果，而不是为了核心算法的操作，因此辅助空间复杂度保持不变。

3. 使用映射或频率数组

当数组元素落在已知、受限范围内时，此方法可能很有帮助。

例如，确定数组的值是否介于 1 到 100 之间。

创建一个与此范围大小相同的新频率数组。最初将其所有组件设置为 0。

• 对于每个元素 x，将频率数组中索引 x 的计数增加 1。
• 如果 frequency_array[x] 已大于 0，则我们之前见过此数字。然后可以将原始数组中的重复项更改为其他值。
• 此方法具有 O(n) 的时间复杂度，非常有效；但是，它需要 O(k) 的空间，其中 k 是值的范围。

输出

Original Array: [22, 33, 44, 22, 33, 66, 11, 88, 44]
After removing duplicates arrays elements: [22, 33, 44, 66, 11, 88]

复杂度分析

时间复杂度

由于代码仅一次遍历大小为 n 的输入数组，因此时间复杂度为 O(n)。在循环内部，HashMap 的 containsKey 和 put 操作平均需要 O(1) 时间。因此，总时间直接与数组中的元素数量成正比，使其成为线性操作。

空间复杂度

由于使用了 HashMap 和辅助数组 temp，因此空间复杂度为 O(n)。在最坏的情况下，输入数组中的所有元素都是唯一的。这意味着 HashMap 将存储 n 个元素，并且在调整大小之前，temp 数组也将存储 n 个元素。这两种结构所需的空间与输入数组的大小成线性比例。

结论

使用集合的平均时间复杂度为 O(n)，由于其简单性和速度，是首选方法。然而，最大的两个缺点是它占用了更多空间并且原始元素的顺序丢失了。由于它使用 O(1) 的额外空间，因此当这是首要任务时，原地排序是最佳选择。 

排序步骤（时间复杂度为 O(n log n)）会减慢其速度并改变原始顺序。使用平均时间复杂度 O(n) 的映射方法是一种快速灵活的选择。如果我们必须执行其他任务，例如计算每个元素出现的次数，那么它特别有用。与集合方法类似，它会占用额外空间，并且不会保留原始顺序。

Java 数组去重 MCQs

1. 使用集合删除重复项的平均时间复杂度为 _______。

1. O(n^2)
2. O(logn)
3. O(n)
4. O(nlogn)

2. 原地排序方法非常适合 _______ 是主要限制的情况。

1. 速度
2. 原始元素顺序
3. 内存
4. 灵活性

3. 原地排序方法的主要缺点是，由于排序步骤，其时间复杂度较高，为 O(nlogn)。

1. O(n)
2. O(nlogn)
3. O(n^2)
4. 以上全部。

4. 当我们需要执行额外任务时，例如计算每个元素的频率，_______ 方法很有用。

1. 使用映射
2. 使用集合
3. 排序数组
4. 以上全部。

5. 集合和映射方法的一个主要缺点是它们不会保留原始元素的 _______。

1. 值
2. 数据类型
3. 顺序
4. 频率