88. Merge Sorted Array

题目描述和难度

  • 题目描述:

给定两个有序整数数组 nums1 nums2,将 nums2 合并到 nums1 使得 num1 成为一个有序数组。

说明:

  • 初始化 nums1nums2 的元素数量分别为 mn
  • 你可以假设 nums1 有足够的空间(空间大小大于或等于 m + n)来保存 nums2 中的元素。

示例:

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

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

思路分析

求解关键:教科书上介绍的归并排序需要额外的辅助数组完成归并。这道题的题目中说了“你可以假设 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