Leetcode-088-合并两个有序数组

Leecode-088-合并两个有序数组

题目描述

给你两个有序整数数组 nums1 和 nums2*，请你将 *nums2 合并到 nums1 中，使 nums1 成为一个有序数组。

说明:

• 初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
• 你可以假设 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]

方法一：从头到后双指针

• 跟合并两个链表很类似，这里也用两个指针指向数组的1的开头，数组2的开头

• 跟链表合并不同的是，如果往数组中插入一个元素，为了保证整体的顺序性，需要挪动前后的元素，所以我们要再创建一个数组来保存指针指向的元素。

• 之后比较两个数组中的元素nums1[i]和nums2[j]，将其放到新数组中。

• 这种两两合并的好处是可以免掉排序了，比较完之后再放到新数组中，元素都是有序的了。

• 但题目要求是在数组1的基础上进行修改，而不是返回一个新数组，所以我们还得把排序好的新数组内容，再重新赋给数组1。

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // 迭代新开的数组
        int i = 0;
        // 双指针
        int j = 0;
        int k = 0;

        int[] arr = new int[m + n];


        while (j < m || k < n){
            // 两个边界条件 j = m  和 k = n
            if (j == m){
                // nums1走完了
                arr[i++] = nums2[k++];
            }else if (k == n){
                // nums2走完了
                arr[i++] = nums1[j++];
            }else if (nums1[j] <= nums2[k]){
                arr[i++] = nums1[j++];
            }else {
                arr[i++] = nums2[k++];
            }
        }

        // 再把数组重新赋值给nums1
        for (int l = 0; l < arr.length; l++) {
            nums1[l] = arr[l];
        }
    }
}

复杂度分析：

• 时间复杂度：O(m + n) 遍历两个数组需要的时间
• 空间复杂度： O(m + n) 新开了一个数组大小

方法二：从后向前迭代数组（空间优化）

• 虽然方法一已经很ok了，但是仔细想想，nums1后面那些个0我们是不是没有用呢？

• 另外题目中也说明了，数组1的空间是足够的，它可以完全容纳下数组1的m个元素和数组2的n个元素。

• 这两个条件拼在一起，我们就有了新的比较方式，即：反着比较。

思路：

• 反向比较nums1[m - 1] 和 nums2[n - 1]
• 注意:这样我们就不需要额外的空间了，数组1后面空着的我们都可以直接用
• 关键：把两个数组后面最大的数放到数组1的最后一位
• 依次类推直到两个数组的元素全部比较完。
  最后数组1就是有序的，这种比较方式不需要再占用额外的空间。

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1;
        int j = n - 1;
        // 用于修改元素的指针
        int k = m + n -1;

        while (i >= 0 || j >= 0){
            // 注意边界条件， i < 0以及 j < 0,这表示一个数组已经使用完了
            if (i < 0){
                nums1[k--] = nums2[j--];
            }else if (j < 0){
                nums1[k--] = nums1[i--];
            }
            // 反向比较的话，拷贝的是较大的元素
            else if (nums1[i] <= nums2[j]){
                nums1[k--] = nums2[j--];
            }else {
                nums1[k--] = nums1[i--];
            }
        }
    }
}

• 时间复杂度：O(m + n) 遍历两个数组需要的时间
• 空间复杂度： O(1)

打赏