数组去重与合并：一维数组去重算法，两个有序数组合并为一个有序数组
数组去重和合并，这两个操作在实际开发中太常见了。我记得刚入行那会儿，写了个数据采集程序，结果从传感器读回来的数据里全是重复值，直接导致后续统计报表炸了。从那以后，我养成了一个习惯——处理数据前，先问问自己：这里需不需要去重？
今天咱们就把这两个核心操作掰开揉碎，讲清楚。你想想看，去重和合并，本质上都是在处理数据的「集合」关系。一个管的是「不要重复」，一个管的是「怎么拼起来」。但两者有个共同点——都依赖数组的有序性。
一维数组去重算法
去重，说白了就是把数组里重复的元素干掉，只留一个。最简单的思路是什么？拿一个元素，跟后面所有的比一遍，发现重复就删掉。但这样做效率太低了，时间复杂度 O(n²)。
我个人习惯用「双指针法」来处理有序数组的去重。为什么强调有序？因为有序数组里，重复元素一定是挨在一起的。这就给了我们一个偷懒的机会——不用每个元素都跟后面所有元素比，只需要跟紧挨着的那个比就行。
核心思路：
- 用两个指针，一个慢指针 i 指向「已去重区域的最后一个位置」，一个快指针 j 遍历整个数组
- 当 arr[j] != arr[i] 时，说明遇到了新元素，把 arr[j] 放到 i+1 的位置，然后 i 和 j 都往前走
- 当 arr[j] == arr[i] 时，说明是重复元素，跳过，只让 j 往前走
// 有序数组去重，返回去重后的新长度
int removeDuplicates(int arr[], int n) {
if (n == 0) return 0;
int i = 0; // 慢指针，指向最后一个不重复元素
for (int j = 1; j < n; j++) {
if (arr[j] != arr[i]) {
i++;
arr[i] = arr[j]; // 把新元素搬过来
}
// 相等的情况，j继续往前走，i不动
}
return i + 1; // 返回去重后的长度
}这段代码跑完，数组的前面部分就是去重后的结果。我曾在一次日志分析项目中用过这个思路，几万条IP地址去重，跑起来飞快。你想想看，如果不用双指针，用那种「发现重复就整体前移」的方法，每次删除都要移动大量元素，性能差太多了。
小技巧：如果数组是无序的，可以先排序再去重。排序用快速排序 O(n log n)，去重用双指针 O(n)，整体比直接暴力去重 O(n²) 快得多。
两个有序数组合并为一个有序数组
合并有序数组，这个操作我几乎每个项目都会用到。比如合并两个按时间排序的日志文件，或者合并两个按分数排序的成绩单。核心思路其实很简单——像拉链一样，两个数组各出一个指针，谁小谁先走。
嗯，这里要注意：合并的时候，我们通常是从前往后比，但如果你想把合并结果直接放到第一个数组里（假设第一个数组空间够大），那就得从后往前比。为什么？因为从前往后比会覆盖掉还没处理的元素。我曾经在这个坑里摔过一次，调试了半天才发现是覆盖问题。
// 合并两个有序数组，结果放到 arr1 中
// 假设 arr1 有足够空间（n1 + n2）
void mergeSortedArrays(int arr1[], int n1, int arr2[], int n2) {
int i = n1 - 1; // arr1 的最后一个有效元素
int j = n2 - 1; // arr2 的最后一个有效元素
int k = n1 + n2 - 1; // 合并后的最后一个位置
// 从后往前比较，谁大谁放到后面
while (i >= 0 && j >= 0) {
if (arr1[i] > arr2[j]) {
arr1[k] = arr1[i];
i--;
} else {
arr1[k] = arr2[j];
j--;
}
k--;
}
// 如果 arr2 还有剩余，全部搬过来
while (j >= 0) {
arr1[k] = arr2[j];
j--;
k--;
}
// 如果 arr1 还有剩余，不用管，它们已经在正确位置了
}这段代码的精妙之处在于「从后往前」这个思路。我刚开始学的时候总觉得别扭，明明从前往后更符合直觉啊。但后来在项目中处理一个内存受限的嵌入式设备时，发现从后往前合并可以省掉一个临时数组，省了不少内存。说白了，有时候反着来反而更高效。
避坑指南：我曾经在合并时忘记处理「剩余元素」的情况。比如 arr2 比 arr1 长，arr1 都处理完了，arr2 还剩一堆。这时候必须把 arr2 剩下的元素全部搬过来。否则合并结果会丢失数据，而且你还不容易发现，因为数组长度看起来是对的。
知识体系总览
下面这张图把去重和合并的核心逻辑串起来了。你看，两个操作都依赖「有序」这个前提，都用到了「双指针」这个技巧。区别在于：去重是「跳过重复」，合并是「比较大小」。
综合示例：先合并再去重
有时候我们会遇到更复杂的场景：两个有序数组合并后，还要去重。比如合并两个用户ID列表，每个列表内部已经有序且无重复，但两个列表之间有重叠。这时候可以合并完再去重，也可以合并过程中直接去重。
我个人更推荐后者——在合并的同时做去重。因为这样只需要遍历一次，效率更高。具体做法是：合并时，如果发现两个数组当前元素相等，只取一个，然后两个指针都往前走。
// 合并两个有序无重复数组，结果也无重复
int mergeAndRemoveDuplicates(int arr1[], int n1, int arr2[], int n2, int result[]) {
int i = 0, j = 0, k = 0;
while (i < n1 && j < n2) {
if (arr1[i] < arr2[j]) {
result[k++] = arr1[i++];
} else if (arr1[i] > arr2[j]) {
result[k++] = arr2[j++];
} else {
// 相等，只取一个，两个指针都走
result[k++] = arr1[i++];
j++;
}
}
// 处理剩余元素
while (i < n1) result[k++] = arr1[i++];
while (j < n2) result[k++] = arr2[j++];
return k; // 返回合并去重后的长度
}你看，代码其实不复杂。关键是要想清楚边界条件：什么时候取 arr1 的，什么时候取 arr2 的，什么时候两个都取但只存一个。我在一个数据清洗工具里用过这个逻辑，处理几百万条记录，跑下来也就几百毫秒。
实用建议：如果你不确定数组里有没有重复，可以先调用去重函数，再调用合并函数。虽然多了一次遍历，但代码更清晰，不容易出错。等性能成为瓶颈时，再考虑合并成一次遍历。
好了，数组去重和合并就讲到这里。这两个操作看似简单，但用好了能解决很多实际问题。下次你写代码处理数据时，不妨想想：能不能先排序？能不能用双指针？很多时候，换个角度，效率就上来了。