HomeArchivesCategoriesLabelMomentsPhotosLinkAbout

LeetCode 88. 合并两个有序数组

学习
52
0
0
2022-04-29
LeetCode 88. 合并两个有序数组

LeetCode 88. 合并两个有序数组

问题描述

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。 初始化 nums1 和 nums2 的元素数量分别为 m 和 n。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。

示例 1：

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

示例 2：

输入：nums1 = [1], m = 1, nums2 = [], n = 0 输出：[1]

提示：

  • nums1.length == m + n

  • nums2.length == n

  • 0 <= m, n <= 200

  • 1 <= m + n <= 200

  • -10^9 <= nums1[i], nums2[i] <= 10^9

进阶：你可以设计实现一个时间复杂度为 O(m + n)、空间复杂度为 O(1) 的算法解决此问题吗？

思路

方法一：归并算法

本题比较容易想到的算法是归并排序中的一次归并算法，其具体步骤如下：

  1. 先创建一个长度为 m + n 的临时一维数组 tmpArr；

  2. 每次从 nums1 和 nums2 中取出一个元素进行比较，将较小者放入 tmpArr，最后将各段中余下的部分直接复制到 tmpArr 中；

  3. 这样 tmpArr 就是一个有序表，最后再将其复制到 nums1 中即可。

方法二：合并后排序

本思路较为简单粗暴，先将数组 nums2 添加到数组 nums1 的尾部，然后直接对 nums1 进行排序即可。

方法三：原地归并

本方法的时间复杂度为 O(m + n)、空间复杂度为 O(1)。

代码实现（Java）

方法一：归并算法

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int[] tmpArr = new int[m + n];
        int i = 0;
        int j = 0;
        int k = 0;
        while (i < m && j < n) {
            if (nums1[i] <= nums2[j]) {
                tmpArr[k++] = nums1[i++];
            } else {
                tmpArr[k++] = nums2[j++];
            }
        }
        if (i < m) {
            // 将数组 nums1 中剩余的部分赋值到 tmpArr 中
            System.arraycopy(nums1, i, tmpArr, k, m - i);
        }
        if (j < n) {
            // 将数组 nums2 中剩余的部分赋值到 tmpArr 中
            System.arraycopy(nums2, j, tmpArr, k, n - j);
        }
        // 将 tmpArr 中的元素复制到 nums1[0...m + n - 1] 中
        System.arraycopy(tmpArr, 0, nums1, 0, m + n);
    }
}

方法二：合并后排序

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // 将数组 nums2 添加到数组 nums1 的尾部
        for (int i = 0; i < n; ++i) {
            nums1[m + i] = nums2[i];
        }
        // 直接对 nums1 进行排序
        Arrays.sort(nums1);
    }
}

方法三：原地归并

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;
        while (p1 >= 0 && p2 >= 0) {
            if (nums1[p1] > nums2[p2]) {
                nums1[p] = nums1[p1];
                p1--;
            } else {
                nums1[p] = nums2[p2];
                p2--;
            }
            p--;
        }
        // 将剩余的 nums2 元素复制到 nums1 中
        System.arraycopy(nums2, 0, nums1, 0, p2 + 1);
    }
}

总结

本题的解法有多种选择，可以根据需要和题目要求选择合适的方法。希望这个解题思路对你有所帮助。

#LeetCode 9