88. Merge Sorted Array

题目描述和难度

• 题目描述：

输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

输出: [1,2,2,3,5,6]

• 题目难度：简单。
• 英文网址：88. Merge Sorted Array 。
• 中文网址：88. 合并两个有序数组 。

思路分析

求解关键：教科书上介绍的归并排序需要额外的辅助数组完成归并。这道题的题目中说了“你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。”，这让我们想到了，其实我们可以从后向前进行归并，谁大谁出列到 nums1 的末尾，这样就不用开辟额外的空间了。我想这道题应该就是考查我们往这个方向思考的。

• 合并两个有序数组的写法，基本上模式是固定的，因为合并以后的元素个数是知道的，每次比较都能确定一个元素的值，并且我们还会先考虑其中一个数组已经归并完成的情况。

参考解答

参考解答1：推荐的写法。

import java.util.Arrays;

public class Solution {

    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int len = m + n;
        int i = m - 1;
        int j = n - 1;
        for (int k = len - 1; k >= 0; k--) {
            if (i == -1) {
                // i 用完了，j 出列
                nums1[k] = nums2[j];
                j--;
            } else if (j == -1) {
                // j 用完了，i 出列
                nums1[k] = nums1[i];
                i--;
            } else if (nums1[i] >= nums2[j]) {
                // 谁大谁出列
                nums1[k] = nums1[i];
                i--;
            } else {
                assert nums1[i] < nums2[j];
                nums1[k] = nums2[j];
                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;
        Solution solution = new Solution();
        solution.merge(nums1, m, nums2, n);
        System.out.println(Arrays.toString(nums1));
    }
}

参考解答2：按照教科书上归并排序的写法。

public class Solution2 {

    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // 因为要在 num1 上修改，把 nums1 返回回去
        // 因此，把 num1 复制一份
        int[] nums3 = new int[m];
        System.arraycopy(nums1, 0, nums3, 0, m);
        // 数组3
        int i = 0;
        // 数组2
        int j = 0;
        int length = m + n;
        for (int k = 0; k < length; k++) {
            if (i == m) {
                nums1[k] = nums2[j];
                j++;
            } else if (j == n) {
                nums1[k] = nums3[i];
                i++;
            } else if (nums3[i] < nums2[j]) {
                nums1[k] = nums3[i];
                i++;
            } else {
                nums1[k] = nums2[j];
                j++;
            }
        }
    }
}

本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0088-merge-sorted-array ，如果我的题解有错误，或者您有更好的解法，欢迎您告诉我 liweiwei1419@gmail.com 。