每日算法-数组合并

Java数组合并算法详解

引言：为什么数组合并如此重要？

在Java开发中，数组作为最基础的数据结构之一，其合并操作是处理数据时的常见需求。无论是在排序算法（如归并排序的核心步骤）、数据聚合（如合并多个数据源的查询结果），还是在业务逻辑（如合并用户的购物车商品列表）中，数组合并都扮演着关键角色。

数组合并的场景千差万别：有时需要合并两个无序数组（如简单拼接数据），有时需要合并两个有序数组（如归并排序中的子数组合并）；有时可以创建新数组存储结果，有时则需要原地合并（如利用已有空间避免内存浪费）。本文将从“思想本质”出发，系统讲解不同场景下的数组合并算法，帮你掌握从“理解逻辑”到“代码实现”的完整链路。

一、数组合并的核心思想：从“无序”到“有序”

数组合并的核心目标是将两个数组arr1和arr2的所有元素整合到一个新的集合中。根据数组是否有序，合并策略差异显著，我们先从“思想根源”理解两种场景的处理逻辑。

1.1 合并两个无序数组：“简单拼接”思想

场景描述：两个数组元素无序（或无需保持有序性），仅需将所有元素合并到一个新数组中。
核心思想：既然无需考虑顺序，直接创建一个长度为两数组之和的新数组，依次将arr1和arr2的元素“搬运”到新数组即可。
类比理解：如同将两个篮子里的苹果倒进一个更大的篮子，不需要考虑苹果的大小顺序，只需确保所有苹果都被转移。

1.2 合并两个有序数组：“双指针”优化思想

场景描述：两个数组已按相同规则排序（如升序），合并后需保持有序性。
核心思想：若直接拼接后排序（如Arrays.sort()），时间复杂度会升高（排序需O((n+m)log(n+m))）。利用“有序”特性，可通过双指针法实现O(n+m)时间复杂度：

• 用两个指针i和j分别指向arr1和arr2的起始位置；
• 比较arr1[i]和arr2[j]，将较小（或较大）的元素放入结果数组，同时移动对应指针；
• 当一个数组遍历完毕后，将另一个数组剩余元素直接复制到结果数组。

类比理解：如同两个有序队列（如按身高排序的两队人），每次从两队队首选更矮的人加入新队列，直到一队为空，剩下的人直接加入——无需整体排序，效率更高。

二、具体实现：从“逻辑”到“代码”

2.1 合并两个无序数组：基础实现

2.1.1 实现步骤

1. 处理边界条件：若其中一个数组为null或空数组，直接返回另一个数组；
2. 创建结果数组：长度为arr1.length + arr2.length；
3. 复制元素：先将arr1的所有元素复制到结果数组，再复制arr2的元素。

2.1.2 代码实现

import java.util.Arrays;public class ArrayMerge {/*** 合并两个无序数组（基础方法）* @param arr1 第一个数组（可能为null或空）* @param arr2 第二个数组（可能为null或空）* @return 合并后的新数组*/public static int[] mergeUnorderedArrays(int[] arr1, int[] arr2) {// 处理边界条件：若arr1为null或空，返回arr2（需先处理arr2的null情况）if (arr1 == null || arr1.length == 0) {return arr2 == null ? new int[0] : Arrays.copyOf(arr2, arr2.length);}// 若arr2为null或空，返回arr1if (arr2 == null || arr2.length == 0) {return Arrays.copyOf(arr1, arr1.length);}// 创建结果数组，长度为两数组之和int[] result = new int[arr1.length + arr2.length];// 复制arr1元素（0到arr1.length-1）到result的0到arr1.length-1位置System.arraycopy(arr1, 0, result, 0, arr1.length);// 复制arr2元素到result的arr1.length位置开始System.arraycopy(arr2, 0, result, arr1.length, arr2.length);return result;}// 测试方法public static void main(String[] args) {int[] arr1 = {3, 1, 4};int[] arr2 = {2, 5};int[] merged = mergeUnorderedArrays(arr1, arr2);System.out.println(Arrays.toString(merged)); // 输出：[3, 1, 4, 2, 5]}
}

2.1.3 关键说明

• System.arraycopy()：Java原生方法，底层通过C实现，比手动for循环复制效率更高，推荐优先使用；
• 边界处理：必须考虑数组为null或空的情况，否则可能抛出NullPointerException或数组越界异常。

2.2 合并两个有序数组：双指针法（新数组存储）

2.2.1 实现步骤

1. 处理边界条件：同2.1.1；
2. 初始化指针：i=0（arr1指针）、j=0（arr2指针）、k=0（结果数组指针）；
3. 双指针遍历：当i < arr1.length且j < arr2.length时，比较arr1[i]和arr2[j]，将较小值放入result[k]，并移动对应指针（i++或j++）和k++；
4. 复制剩余元素：若i < arr1.length，将arr1剩余元素（i到末尾）复制到result；若j < arr2.length，同理复制arr2剩余元素。

2.2.2 代码实现

/*** 合并两个有序数组（升序），结果存储在新数组中* @param arr1 有序数组1（升序）* @param arr2 有序数组2（升序）* @return 合并后的有序数组*/
public static int[] mergeSortedArrays(int[] arr1, int[] arr2) {// 边界处理if (arr1 == null || arr1.length == 0) {return arr2 == null ? new int[0] : Arrays.copyOf(arr2, arr2.length);}if (arr2 == null || arr2.length == 0) {return Arrays.copyOf(arr1, arr1.length);}int len1 = arr1.length, len2 = arr2.length;int[] result = new int[len1 + len2];int i = 0, j = 0, k = 0; // 三个指针// 双指针遍历，比较并放入较小元素while (i < len1 && j < len2) {if (arr1[i] <= arr2[j]) { // 若相等，优先放arr1元素（保持稳定性）result[k++] = arr1[i++];} else {result[k++] = arr2[j++];}}// 复制剩余元素（最多执行一个）if (i < len1) {System.arraycopy(arr1, i, result, k, len1 - i);}if (j < len2) {System.arraycopy(arr2, j, result, k, len2 - j);}return result;
}// 测试
public static void main(String[] args) {int[] arr1 = {1, 3, 5};int[] arr2 = {2, 4, 6};int[] merged = mergeSortedArrays(arr1, arr2);System.out.println(Arrays.toString(merged)); // 输出：[1, 2, 3, 4, 5, 6]
}

2.2.3 关键说明

• 稳定性：当arr1[i] == arr2[j]时，优先放入arr1元素，可保持原数组中相等元素的相对顺序（稳定合并）；
• 效率：每个元素仅比较一次，遍历一次，时间复杂度O(n+m)，空间复杂度O(n+m)（结果数组）。

2.3 合并两个有序数组：原地合并（LeetCode 88题场景）

2.3.1 场景特殊性

有时需合并到arr1中（如arr1有足够空间：arr1.length = m + n，其中前m个为有效元素，后n个为0，需合并arr2（长度n）并保持有序）。此时若从前往后合并，可能覆盖arr1未处理的元素，需从后往前双指针。

2.3.2 实现步骤

1. 初始化指针：i = m - 1（arr1有效元素末尾）、j = n - 1（arr2末尾）、k = m + n - 1（arr1末尾，即结果数组末尾）；
2. 后向双指针遍历：当i >= 0且j >= 0时，比较arr1[i]和arr2[j]，将较大值放入arr1[k]，并移动对应指针（i--或j--）和k--；
3. 复制剩余元素：若j >= 0（arr2有剩余元素），将arr2[j]到arr2[0]复制到arr1[k]到arr1[0]。

2.3.3 代码实现

/*** 原地合并两个有序数组（LeetCode 88题）* @param nums1 第一个数组（长度m+n，前m个有效元素，升序）* @param m  nums1有效元素个数* @param nums2 第二个数组（长度n，升序）* @param n  nums2元素个数*/
public static void mergeSortedArraysInPlace(int[] nums1, int m, int[] nums2, int n) {int i = m - 1; // nums1有效元素末尾指针int j = n - 1; // nums2末尾指针int k = m + n - 1; // 结果数组末尾指针（nums1末尾）// 后向遍历，比较并放入较大元素while (i >= 0 && j >= 0) {if (nums1[i] > nums2[j]) {nums1[k--] = nums1[i--];} else {nums1[k--] = nums2[j--];}}// 若nums2有剩余元素，复制到nums1开头（nums1剩余元素已在正确位置）while (j >= 0) {nums1[k--] = nums2[j--];}
}// 测试
public static void main(String[] args) {int[] nums1 = {1, 2, 3, 0, 0, 0};int m = 3;int[] nums2 = {2, 5, 6};int n = 3;mergeSortedArraysInPlace(nums1, m, nums2, n);System.out.println(Arrays.toString(nums1)); // 输出：[1, 2, 2, 3, 5, 6]
}

2.3.4 关键说明

• 避免覆盖：从后往前合并，arr1未处理的元素在左侧，arr2元素在右侧，不会覆盖；
• 空间优化：无需额外数组，空间复杂度O(1)，时间复杂度仍为O(n+m)。

三、算法对比与选择建议

合并场景	核心方法	时间复杂度	空间复杂度	适用场景
无序数组合并	简单拼接	O(n+m)	O(n+m)	无需保持顺序，如日志数据拼接
有序数组合并（新数组）	前向双指针	O(n+m)	O(n+m)	允许额外空间，需稳定合并
有序数组合并（原地）	后向双指针	O(n+m)	O(1)	有足够空间，需节省内存

选择建议：

• 无序数组：直接用“简单拼接”；
• 有序数组：优先用“双指针法”（新数组），若有原地合并需求（如arr1有空间），用“后向双指针”。

四、常见问题与解决方案

4.1 边界条件遗漏

问题：未处理null或空数组，导致NullPointerException或数组越界。
解决：合并前显式判断数组是否为null或长度为0，直接返回另一个数组。

4.2 有序数组合并时用“拼接+排序”

问题：对有序数组先拼接再用Arrays.sort()，时间复杂度升高至O((n+m)log(n+m))。
解决：牢记“有序数组用双指针”，利用有序性优化效率。

4.3 原地合并时从前往后遍历

问题：覆盖arr1未处理元素（如nums1 = [1,3,5,0,0,0]，nums2 = [2,4,6]，从前往后会覆盖3、5）。
解决：必须从后往前遍历，用后向双指针。

五、应用场景举例

1. 归并排序：核心步骤是合并两个有序子数组，正是本文“双指针法”的典型应用；
2. 数据库查询结果合并：若两个查询结果按时间戳排序，可合并为一个有序结果集；
3. 日志分析：合并两个按时间排序的日志文件，快速生成完整时间线；
4. 电商购物车合并：合并用户在不同设备的购物车，按商品价格或加入时间排序。

总结

数组合并看似简单，实则蕴含“场景适配”和“效率优化”的思考。无序数组的“简单拼接”是基础，有序数组的“双指针法”是核心（时间O(n+m)），原地合并的“后向双指针”是进阶技巧（空间O(1)）。掌握这些方法，不仅能解决实际问题，更能培养“利用数据特性优化算法”的思维——这正是编程能力的核心。