数组去重:双指针法的优雅实现
在日常开发中,数组去重是一个常见的需求。无论是处理用户输入、数据清洗,还是优化算法性能,去重操作都扮演着重要角色。本文将介绍一种高效的去重方法——双指针法,并结合代码示例,帮助你轻松掌握这一技巧。
1. 问题描述
给定一个包含重复元素的数组,要求删除重复项,返回一个不包含重复元素的新数组。例如:
- 输入:
[4, 3, 2, 4, 1, 3, 5, 6, 5]
- 输出:
[1, 2, 3, 4, 5, 6]
2. 思路分析
2.1 排序的重要性
在去重之前,首先对数组进行排序。排序后,相同的元素会被排列在一起,这为后续的去重操作提供了便利。
2.2 双指针法的原理
双指针法是一种高效的算法技巧,尤其适用于有序数组的操作。其核心思想如下:
- 慢指针(
i
):指向当前不重复的元素。 - 快指针(
j
):遍历整个数组,寻找新元素。 - 如果
arr[j]
和arr[i]
相同,说明有重复,跳过j
。 - 如果
arr[j]
和arr[i]
不同,说明arr[j]
是一个新元素,将其赋值给arr[i+1]
,然后i
向前移动。
通过这种方式,可以在线性时间内完成去重操作。
3. 代码实现
以下是基于双指针法的数组去重实现:
import java.util.Arrays;
public class ArrayDuplicateRemover {
public static void main(String[] args) {
int[] arr = {4, 3, 2, 4, 1, 3, 5, 6, 5};
// 1. 先对数组进行排序
Arrays.sort(arr);
System.out.println("Sorted array: " + Arrays.toString(arr));
// 2. 使用双指针法去重
int[] result = removeDuplicates(arr);
System.out.println("Array after removing duplicates: " + Arrays.toString(result));
}
public static int[] removeDuplicates(int[] arr) {
if (arr == null || arr.length == 0) {
return arr;
}
int i = 0; // 慢指针
// 快指针 j 从 1 开始遍历
for (int j = 1; j < arr.length; j++) {
// 如果当前元素与慢指针指向的元素不同,说明是新元素
if (arr[j] != arr[i]) {
i++; // 慢指针向前移动
arr[i] = arr[j]; // 将新元素赋值给慢指针的下一个位置
}
}
// 返回去重后的数组(截取前 i+1 个元素)
return Arrays.copyOf(arr, i + 1);
}
}
4. 代码解析
4.1 排序
- 使用
Arrays.sort(arr)
对数组进行排序。 - 排序后,相同的元素会排列在一起,便于后续去重。
4.2 双指针法
- 慢指针
i
:初始值为0
,指向当前不重复的元素。 - 快指针
j
:从1
开始遍历数组,寻找新元素。 - 如果
arr[j] != arr[i]
,说明arr[j]
是一个新元素,将其赋值给arr[i+1]
,然后i
向前移动。
4.3 返回结果
- 使用
Arrays.copyOf(arr, i + 1)
截取去重后的数组。
5. 示例运行
输入
int[] arr = {4, 3, 2, 4, 1, 3, 5, 6, 5};
输出
Sorted array: [1, 2, 3, 3, 4, 4, 5, 5, 6]
Array after removing duplicates: [1, 2, 3, 4, 5, 6]
6. 复杂度分析
6.1 时间复杂度
- 排序:
O(n log n)
。 - 双指针遍历:
O(n)
。 - 总时间复杂度:
O(n log n)
。
6.2 空间复杂度
- 只使用了常数级别的额外空间,空间复杂度为
O(1)
。
7. 总结
双指针法是一种非常优雅且高效的去重方法,尤其适用于有序数组。通过排序和双指针的结合,我们可以在 O(n log n)
的时间复杂度内完成去重操作,同时保持空间复杂度为 O(1)
。