首页 文章详情

每日一道 LeetCode (19):合并两个有序数组

极客挖掘机 | 287 2020-08-15 10:35 0 0 0
UniSMS (合一短信)

每天 3 分钟,走上算法的逆袭之路。

前文合集

每日一道 LeetCode 前文合集

代码仓库

GitHub:https://github.com/meteor1993/LeetCode

Gitee:https://gitee.com/inwsy/LeetCode

题目:合并两个有序数组

题目来源:https://leetcode-cn.com/problems/merge-sorted-array/

给你两个有序整数数组 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]

解题方案

这道题单纯的从排序上来讲并不是难题,毕竟题目中已经给出来两个有序的数组了,最简单的循环一下长数组,然后挨个比较下两个数组元素的大小,放到一个新数组里面就完事儿了。

这道题的难点在于,我们需要在 nums1 数组中,完成两个数组的排序,这个就稍微有点坑了,这相当于要把 nums2 合并到 nums1 当中,还得要有序的合并进去。

这个弯有点难绕的,题目中虽然说最终的结果要在 nums1 当中,但是并没有说不允许我们创建第三个数组啊,我可以创建一个新的数组,把 nums1 copy 到新的数组中,然后再在 nums1 当中完成排序,这不也行么。

接下来就是代码时间,很简单,定义了两个指针,一个是 copy_nums1 的指针,还有一个是 nums2 的指针,通过移动这两个指针,来完成整个排序工作。

// 从前往后
public void merge(int[] nums1, int m, int[] nums2, int n) {
    int[] copy_nums1 = new int[m];
    System.arraycopy(nums1, 0, copy_nums1, 0, m);

    // copy_nums1 的指针
    int n1 = 0;
    // nums2 的指针
    int n2 = 0;
    // nums1 的指针
    int n0 = 0;

    while ((n1 < m) && (n2 < n)) {
        nums1[n0++] = copy_nums1[n1] < nums2[n2] ? copy_nums1[n1++] : nums2[n2++];
    }

    if (n1 < m) {
        System.arraycopy(copy_nums1, n1, nums1, n1 + n2, m + n - n1 - n2);
    }
    if (n2 < n) {
        System.arraycopy(nums2, n2, nums1, n1 + n2, m + n - n1 - n2);
    }
}

上面这种方案虽说能解决问题,但是有一点不大好,就是新建了一个数组,多占用了一个数组的空间,既然题上说 nums1 的长度足够上,我们从小到大排序不好排,那么如果是从大到小呢?

思路基本上还是一个思路,定义两个指针,然后倒序的将元素装到 nums1 里面。

// 从后往前
public void merge_1(int[] nums1, int m, int[] nums2, int n) {
    // nums1 有数据的尾部指针
    int n1 = m - 1;
    // nums2 的尾部指针
    int n2 = n - 1;
    // nums1 最终的尾部指针
    int n0 = m + n - 1;

    while ((n1 >= 0) && (n2 >= 0)) {
        nums1[n0--] = nums1[n1] < nums2[n2] ? nums2[n2--] : nums1[n1--];
    }

    System.arraycopy(nums2, 0, nums1, 0, n2 + 1);
}

今天这两道题都不难,基本上搞清楚了方案以后,就是写写代码练练手。

感谢阅读



good-icon 0
favorite-icon 0
收藏
回复数量: 0
    暂无评论~~
    Ctrl+Enter