小白水平理解面试经典题目LeetCode 88 Merge Sorted Array【Java实现】

发布时间:2024年01月19日

88. 合并排序数组

你好,今天做的是leetcode 88题,是一道数组类题目,它也是总被问道的一个类型。

题目描述

给定两个有序整数数组 nums1 和 nums2,将 nums2 合并到 nums1 中,使 nums1 成为一个有序数组。
初始化 nums1 和 nums2 都为空,且 nums1 的长度为 m + n。
将 nums1 和 nums2 合并到按非降序排序的单个数组中。
最终排序的数组不应由函数返回,而应存储在数组 nums1 内。为了适应这种情况, nums1 的长度为 m + n ,其中第一个 m 元素表示应合并的元素,最后的值如果设置为0,应被忽略。 nums2 的长度为 n 。

例子

在这里插入图片描述

这里我个人小白理解分析:

在这里插入图片描述
思考1:如果只需一次考虑两个元素而不是两个数组,则可以轻松解决此问题。

我们都知道每个单独的数组都是有序的。我们不知道的是它们将如何交织在一起。我们能否做出局部决策并得出最佳解决方案?

猛一看,这类题好像是一个常规合并,返回一个结果数组即可。暴力解法走起,只要把nums2 数组中的元素先遍历的放入nums1数组中,完事儿后,并进行一个从小到大的升序排列。内心露出一抹喜色,怎么样,终于把隔壁班女生联系方式要到了。
在这里插入图片描述

解题环节

上来咱就是主打一个快,别让面试官久等了。

public static int[] merge1(int[] nums1, int m, int[] nums2, int n) {
    // 将两个数组合并到一个数组中
    for (int i = 0; i < n; i++) {
        nums1[m + i] = nums2[i];
    }

    // 对合并后的数组进行排序
    Arrays.sort(nums1);
    return nums1;
}

小明:OK,完事儿,等着面试官来表扬自己吧。他肯定会说:小子,你是个好手!工位都给你准备好了,工资你说了算。

面试官:嗯,你这个要是nums2 给了十万个数是不是会影响性能?

小明OS:今年这个找工市场,人言洛阳花似锦,偏我来时不逢春。。。怎的,技能要求突然涨了,不是做出来就行?

好吧,逼我拿出压箱底的东西是吧。的确这个算法是偏慢。

话不多说,拿图说话。
在这里插入图片描述
我们可以把nums2数组中的内容去和nums1中做对比,这样可以不仅可以节省时间,也可以节省内存,相当于对nums1数组内容直接进行替换。具体步骤如下。

  • Step1. 既然要将最终输出结果放入nums1数组,我们定义出一个last index

  • Step2. 要确保m 和 n都是大于0,而从中找到两个数组中的最大值,将它放入结果中。

  • Step3. 这中间要考虑m, n的递减问题

  • Step4. 最后,把nums2数组中的剩余值放到nums1中

Java

public static int[] merge2(int[] nums1, int m, int[] nums2, int n) {
        // 结果nums1的最后一项
        int last = m + n - 1;

        // 方向融合
        while (m > 0 && n > 0) {
            if (nums1[m - 1] > nums2[n - 1]) {
                nums1[last] = nums1[m - 1];
                m -= 1;
            } else {
                nums1[last] = nums2[n - 1];
                n -= 1;
            }
            last -= 1;
        }

        // 将nums2中的剩余元素填入nums1
        while (n > 0) {
            nums1[last] = nums2[n - 1];
            n = n - 1;
            last = last - 1;
        }
        return nums1;
    }

好了,时间复杂度O(logn)了,下一面继续
在这里插入图片描述
编码道路漫漫,只要先看脚下的路,徐徐前进即可。

文章来源:https://blog.csdn.net/u014739136/article/details/135661332
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。