PiggyBlog
0%
Published on

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

Authors

✨ 题目介绍

给你两个 升序排列 的整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使得 nums1 成为一个升序数组。

  • 初始时，nums1 的长度为 m + n，其中前 m 个元素为有效元素，后 n 个元素为 0（占位）。
  • nums2 的长度为 n。

你需要 就地修改 nums1，不能返回新数组。

LeetCode 中的经典题目：88. Merge Sorted Array

💡 题目思路

我们可以使用双指针归并排序思想，维护两个指针分别指向 nums1 和 nums2 的当前比较元素。

  • 指针 i 初始指向 nums1 的第一个有效元素
  • 指针 j 初始指向 nums2 的第一个元素
  • 比较两者的大小，较小的元素放入新的位置数组 mergedArray
  • 最后将 mergedArray 复制回 nums1

注意：

  • 原地合并（不借助额外数组）的方法会更优，本文在“优化方案”部分介绍。

🧮 思路演示

举个例子：

nums1 = [1,3,5,0,0,0], m = 3
nums2 = [2,4,6], n = 3

合并步骤如下：

  1. 比较 1 和 2，取 1
  2. 比较 3 和 2，取 2
  3. 比较 3 和 4，取 3
  4. 比较 5 和 4，取 4
  5. 比较 5 和 6，取 5
  6. nums2 还剩 6，放入

最终：nums1 = [1,2,3,4,5,6]

💻 题目代码实现（含测试）

import java.util.Arrays;

public class ProblemMergeSortedArray {

    public static void merge(int[] nums1, int m, int[] nums2, int n) {
        if (nums1 == null || nums2 == null) {
            throw new IllegalArgumentException("Input arrays must not be null!");
        }
        if (m < 0 || n < 0) {
            throw new IllegalArgumentException("Length parameters must be non-negative!");
        }
        if (m + n > nums1.length) {
            throw new IllegalArgumentException("nums1 Length is insufficient to hold merged result!");
        }
        if (m > nums1.length || n > nums2.length) {
            throw new IllegalArgumentException("Length parameter exceed actual array length!");
        }

        int nums1Index = 0, nums2Index = 0, mergedIndex = 0;
        int[] mergedArray = new int[m + n];

        while (nums1Index < m && nums2Index < n) {
            if (nums1[nums1Index] < nums2[nums2Index]) {
                mergedArray[mergedIndex++] = nums1[nums1Index++];
            } else {
                mergedArray[mergedIndex++] = nums2[nums2Index++];
            }
        }

        while (nums1Index < m) {
            mergedArray[mergedIndex++] = nums1[nums1Index++];
        }

        while (nums2Index < n) {
            mergedArray[mergedIndex++] = nums2[nums2Index++];
        }

        System.arraycopy(mergedArray, 0, nums1, 0, m + n);
    }

    public static void testMerge(String testName, int[] nums1, int m, int[] nums2, int n, int[] expected) {
        System.out.println("=== Test Case: " + testName + " ===");
        try {
            int[] originalNums1 = nums1 != null ? Arrays.copyOf(nums1, nums1.length) : null;

            if (expected == null) {
                try {
                    merge(nums1, m, nums2, n);
                    System.out.println("FAIL - Expected exception but none thrown");
                } catch (Exception e) {
                    System.out.println("PASS - Caught expected exception: " + e.getClass().getSimpleName() + " - " + e.getMessage());
                }
            } else {
                merge(nums1, m, nums2, n);
                if (Arrays.equals(nums1, expected)) {
                    System.out.println("PASS");
                } else {
                    System.out.println("FAIL");
                }
                System.out.println("Input nums1: " + Arrays.toString(originalNums1) + ", m: " + m);
                System.out.println("Input nums2: " + Arrays.toString(nums2) + ", n: " + n);
                System.out.println("Expected:    " + Arrays.toString(expected));
                System.out.println("Actual:      " + Arrays.toString(nums1));
            }
        } catch (Exception e) {
            System.out.println("FAIL - Unexpected exception: " + e.getMessage());
        }
    }

    public static void main(String[] args) {
        // ✅ 正常情况测试
        testMerge("Both arrays with elements",
                new int[]{1, 3, 5, 0, 0, 0}, 3,
                new int[]{2, 4, 6}, 3,
                new int[]{1, 2, 3, 4, 5, 6});

        testMerge("nums1 empty",
                new int[]{0, 0, 0}, 0,
                new int[]{2, 4, 6}, 3,
                new int[]{2, 4, 6});

        testMerge("nums2 empty",
                new int[]{1}, 1,
                new int[]{}, 0,
                new int[]{1});

        testMerge("All elements same",
                new int[]{2, 2, 2, 0, 0}, 3,
                new int[]{2, 2}, 2,
                new int[]{2, 2, 2, 2, 2});

        testMerge("With duplicates",
                new int[]{1, 2, 3, 0, 0, 0}, 3,
                new int[]{2, 5, 6}, 3,
                new int[]{1, 2, 2, 3, 5, 6});

        // ❌ 异常情况测试
        testMerge("nums1 is null", null, 0, new int[]{1, 2}, 2, null);
        testMerge("nums2 is null", new int[]{1, 2, 0}, 2, null, 1, null);
        testMerge("m is negative", new int[]{1, 2, 0}, -1, new int[]{3}, 1, null);
        testMerge("n is negative", new int[]{1, 2, 0}, 2, new int[]{3}, -1, null);
        testMerge("nums1 too short", new int[]{1, 2}, 2, new int[]{3, 4}, 2, null);
        testMerge("m exceeds nums1 length", new int[]{1, 2}, 3, new int[]{3}, 1, null);
        testMerge("n exceeds nums2 length", new int[]{1, 2, 0}, 2, new int[]{3}, 2, null);
    }
}

⏱️ 时间和空间复杂度分析

  • 时间复杂度：O(m + n) 每个元素都只遍历了一次。
  • 空间复杂度：O(m + n) 使用了一个额外数组 mergedArray 存储合并结果。

🚀 算法优化方案（更好的写法）

题目要求在 nums1 原地修改。我们可以 从后往前遍历，这样就能直接在 nums1 中放置最大元素，无需额外数组：

public void merge(int[] nums1, int m, int[] nums2, int n) {
    int i = m - 1, j = n - 1, k = m + n - 1;

    while (i >= 0 && j >= 0) {
        nums1[k--] = nums1[i] > nums2[j] ? nums1[i--] : nums2[j--];
    }

    while (j >= 0) {
        nums1[k--] = nums2[j--];
    }
}
  • 时间复杂度仍为 O(m + n)
  • 空间复杂度为 O(1)，无需额外数组

✅ 总结

  • 本题本质是归并排序的合并过程。
  • 初始写法逻辑清晰但使用了额外数组，可以作为理解算法的第一步。
  • 最终推荐使用从后向前原地合并的方法，提升空间效率。
View on GitHub