当前位置：首页 > news >正文

LeetCode CodeTop 88.合并两个有序数组

news 2026/6/11 19:12:53

思路：

1.错误思路：如果从左往右地把nums2合并到nums1中，假设nums2[0] < nums1[0]，那么nums2[0]会直接覆盖掉nums1[0]，这不是我们期望看到的。

2.正确思路：从右往左地把nums2合并到nums1中，举例如下：

（1）nums1 = [1,2,3,*,*,*]，nums2 = [4,5,6]。这里我用 * 表示可以填入的空位。在这个例子中，nums2可以直接填入nums1后面的3个空位，得到[1,2,3,4,5,6]，没有任何错误覆盖。

（2）nums1 = [1,2,6,*,*,*]，nums2 = [3,4,5]。这里nums1中的6是最大的，应当填入末尾。现在nums1 = [1,2,*,*,*,6]，注意nums2现在这个位置空出了。然后把nums2中的数字填入空位，得到[1,2,3,4,5,6]，没有任何错误覆盖。

（3）上面的例子表明，把nums1中的数字移到另一个空位上，又产生了一个新的空位，所以剩余空位的个数是不变的，我们总是有空位可以让nums2的数字填入，不会发生错误覆盖，这是如下算法正确的前提。

3.算法：

（1）初始化3个指针，p1 = m - 1指向nums1的末尾，p2 = n - 1指向nums2的末尾，p = m + n - 1指向合并后的数组末尾。

（2）不断比较nums1[p1]和nums2[p2]的大小，将较大的值放入nums1[p]。如果p1 >= 0且nums1[p1]更大，那么放入后p1和p减1，否则p2和p减1。注意nums1[p1] == nums2[p2]时放入谁都可以，不妨规定放入nums2[p2]，这样在数组元素都相等的情况下，只需要把nums2的数据填入nums1中，效率更高。

（3）循环直到p2 < 0，此时nums2的所有元素均已填入nums1。你可能会想，如果nums1还有元素没有移动呢？注意到当nums2都合并到nums1中时，nums1剩余未移动的元素，它要移动的目标位置就是它自己所处的位置，所以无需移动，合并完毕。这可以算作一个小优化，比如nums1 = [1,2,3,*,*,*]，nums2 = [4,5,6]，其实只要把nums2的所有数都填入nums1中，合并就已经结束了，即便此时p1 = 2仍然 >= 0。

4.复杂度分析：

（1）时间复杂度：O(m + n)，最坏情况下如nums1=[4,5,6,∗,∗,∗],nums2=[1,2,3]，每个数都需要移动一次。

（2）空间复杂度：O(1)。

附代码：

class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { int p1 = m - 1; int p2 = n - 1; int p = m + n - 1; // 说明nums2还有要合并的元素 while(p2 >= 0){ // 如果p1 < 0，那么走else分支，把nums2合并到nums1中 if(p1 >= 0 && nums1[p1] > nums2[p2]){ // 填入nums1[p1] nums1[p--] = nums1[p1--]; }else{ // 填入nums2[p2] nums1[p--] = nums2[p2--]; } } } }

ACM模式：

import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); // 读取 m 和 n int m = scanner.nextInt(); int n = scanner.nextInt(); // 读取 nums1 的前 m 个有效元素，后面 n 个位置为 0 int[] nums1 = new int[m + n]; for (int i = 0; i < m; i++) { nums1[i] = scanner.nextInt(); } // nums1 剩余的位置默认为 0，不需要读取 // 读取 nums2 的 n 个元素 int[] nums2 = new int[n]; for (int i = 0; i < n; i++) { nums2[i] = scanner.nextInt(); } // 调用合并方法 Solution solution = new Solution(); solution.merge(nums1, m, nums2, n); // 输出合并后的 nums1 for (int i = 0; i < m + n; i++) { System.out.print(nums1[i]); if (i < m + n - 1) { System.out.print(" "); } } System.out.println(); scanner.close(); } } class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { int p1 = m - 1; int p2 = n - 1; int p = m + n - 1; // 说明 nums2 还有要合并的元素 while (p2 >= 0) { // 如果 p1 < 0，那么走 else 分支，把 nums2 合并到 nums1 中 if (p1 >= 0 && nums1[p1] > nums2[p2]) { // 填入 nums1[p1] nums1[p--] = nums1[p1--]; } else { // 填入 nums2[p2] nums1[p--] = nums2[p2--]; } } } }

构造测试用例：

import java.util.*; class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { int p1 = m - 1; int p2 = n - 1; int p = m + n - 1; // 说明 nums2 还有要合并的元素 while (p2 >= 0) { // 如果 p1 < 0，那么走 else 分支，把 nums2 合并到 nums1 中 if (p1 >= 0 && nums1[p1] > nums2[p2]) { // 填入 nums1[p1] nums1[p--] = nums1[p1--]; } else { // 填入 nums2[p2] nums1[p--] = nums2[p2--]; } } } } public class Main { public static void main(String[] args) { Solution solution = new Solution(); // 测试用例1：基本合并（两个数组都有元素） System.out.println("测试用例1 - 基本合并"); int[] nums1_1 = {1, 2, 3, 0, 0, 0}; int m1 = 3; int[] nums2_1 = {2, 5, 6}; int n1 = 3; System.out.print("nums1原始: "); System.out.print(Arrays.toString(nums1_1)); System.out.print("nums2: "); System.out.print(Arrays.toString(nums2_1)); solution.merge(nums1_1, m1, nums2_1, n1); System.out.print("合并后: "); System.out.print(Arrays.toString(nums1_1)); System.out.println("期望: [1, 2, 2, 3, 5, 6]"); System.out.println(); } }

查看全文

http://www.gsyq.cn/news/1505726.html