合并两个有序数组(简单)

这篇具有很好参考价值的文章主要介绍了合并两个有序数组(简单)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

合并两个有序数组(简单),算法题,算法,数据结构,java,后端,面试,性能优化,系统架构

一、题目

给你两个按 非递减顺序 排列的整数数组nums1nums2,另有两个整数mn,分别表示nums1nums2中的元素数目。请你 合并 nums2nums1中,使合并后的数组同样按 非递减顺序 排列。

注意: 最终,合并后数组不应由函数返回,而是存储在数组nums1中。为了应对这种情况,nums1的初始长度为m + n,其中前m个元素表示应合并的元素,后n个元素为0,应忽略。nums2的长度为n

示例 1:
输入:nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出:[1,2,2,3,5,6]
解释:需要合并[1,2,3][2,5,6]
合并结果是[1,2,2,3,5,6],其中斜体加粗标注的为nums1中的元素。

示例 2:
输入:nums1 = [1], m = 1, nums2 = [], n = 0
输出:[1]
解释:需要合并[1][]
合并结果是[1]

示例 3:
输入:nums1 = [0], m = 0, nums2 = [1], n = 1
输出:[1]
解释:需要合并的数组是[][1]
合并结果是 [1]
注意,因为m = 0,所以nums1中没有元素。nums1中仅存的0仅仅是为了确保合并结果可以顺利存放到nums1中。

nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-109 <= nums1[i], nums2[j] <= 109

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

二、代码

【1】直接合并后排序: 最直观的方法是先将数组nums2放进数组nums1的尾部,然后直接对整个数组进行排序。

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        for (int i = 0; i != n; ++i) {
            nums1[m + i] = nums2[i];
        }
        Arrays.sort(nums1);
    }
}

时间复杂度: O((m+n)log⁡(m+n))。排序序列长度为m+n,套用快速排序的时间复杂度即可,平均情况为O((m+n)log⁡(m+n))
空间复杂度: O(log⁡(m+n))。排序序列长度为m+n,套用快速排序的空间复杂度即可,平均情况为O(log⁡(m+n))

【2】双指针: 方法一没有利用数组nums1nums2已经被排序的性质。为了利用这一性质,我们可以使用双指针方法。这一方法将两个数组看作队列,每次从两个数组头部取出比较小的数字放到结果中。我们为两个数组分别设置一个指针p1p2来作为队列的头部指针。代码实现如下:

如果从右往左地把nums2合并到nums1中,是否会发生错误的覆盖呢?我们来看几个例子:
1、nums1=[1,2,3,∗,∗,∗],nums2=[4,5,6]。这里我用表示可以填入的空位。在这个例子中,nums2可以直接填入nums1后面的3个空位,得到[1,2,3,4,5,6],没有任何错误覆盖。
2、nums1=[1,2,6,∗,∗,∗],nums2=[3,4,5]。这里nums1中的6是最大的,应当填入末尾。现在nums1=[1,2,∗,∗,∗,6],注意nums1[2]这个位置现在空出了。然后把nums2中的数字填入空位,得到[1,2,3,4,5,6],没有任何错误覆盖。
3、上面的例子表明,把nums1中的数字移到另一个空位,又产生了一个新的空位,所以剩余空位的个数是不变的,我们总是有空位可以让nums2的数字填入,不会发生错误覆盖,这是如下算法正确的前提。

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1 = 0, p2 = 0;
        int[] sorted = new int[m + n];
        int cur;
        while (p1 < m || p2 < n) {
            if (p1 == m) {
                cur = nums2[p2++];
            } else if (p2 == n) {
                cur = nums1[p1++];
            } else if (nums1[p1] < nums2[p2]) {
                cur = nums1[p1++];
            } else {
                cur = nums2[p2++];
            }
            sorted[p1 + p2 - 1] = cur;
        }
        for (int i = 0; i != m + n; ++i) {
            nums1[i] = sorted[i];
        }
    }
}

时间复杂度: O(m+n)。指针移动单调递增,最多移动m+n次,因此时间复杂度为O(m+n)
空间复杂度: O(m+n)。需要建立长度为m+n的中间数组sorted

【3】逆向双指针: 之所以要使用临时变量,是因为如果直接合并到数组nums1中,nums1中的元素可能会在取出之前被覆盖。那么如何直接避免覆盖nums1中的元素呢?观察可知,nums1的后半部分是空的,可以直接覆盖而不会影响结果。因此可以指针设置为从后向前遍历,每次取两者之中的较大者放进nums1的最后面。

严格来说,在此遍历过程中的任意一个时刻,nums1数组中有m−mmax−1个元素被放入nums1的后半部,nums2数组中有n−nmax−1个元素被放入nums1的后半部,而在指针mmax的后面,nums1数组有m+n−mmax−1个位置。由于m+n−mmax−1≥m−mmax−1+n−nmax−1等价于nmax≥−1永远成立,因此mmax后面的位置永远足够容纳被插入的元素,不会产生mmax的元素被覆盖的情况。

class Solution {
    // 解题思路: 如果想重复利用 nums1的内存,可以从后先前替换,这样即不修改nums1之前的数据,还可以节省空间复杂度
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // 先做特殊情况的处理
        int mmax = nums1.length > m ? m : nums1.length;
        int nmax = nums2.length > n ? n : nums2.length;
        // 从限定最大坐标(mmax和nmax)开始判断,将大的值存放到nums1最大的坐标(mmax+nmax)中
        while (mmax > 0 || nmax > 0) {
            // 如果 nmax <= 0 直接去 nums1 的值
            if  (nmax <= 0 || (mmax > 0 && nums1[mmax - 1] > nums2[nmax - 1] )) {
                nums1[mmax + nmax - 1] = nums1[--mmax];
            } else {
                nums1[mmax + nmax - 1] = nums2[--nmax];
            }
        }
    }
}

时间复杂度: O(m+n)。指针移动单调递减,最多移动m+n次,因此时间复杂度为O(m+n)
空间复杂度: O(1)。直接对数组nums1原地修改,不需要额外空间。

【4】标签: 从后向前数组遍历
1、因为nums1的空间都集中在后面,所以从后向前处理排序的数据会更好,节省空间,一边遍历一边将值填充进去。
2、设置指针len1len2分别指向nums1nums2的有数字尾部,从尾部值开始比较遍历,同时设置指针len指向nums1的最末尾,每次遍历比较值大小之后,则进行填充。
3、当len1<0时遍历结束,此时nums2中海油数据未拷贝完全,将其直接拷贝到nums1的前面,最后得到结果数组。

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int len1 = m - 1;
        int len2 = n - 1;
        int len = m + n - 1;
        while(len1 >= 0 && len2 >= 0) {
            // 注意--符号在后面,表示先进行计算再减1,这种缩写缩短了代码
            nums1[len--] = nums1[len1] > nums2[len2] ? nums1[len1--] : nums2[len2--];
        }
        // 表示将nums2数组从下标0位置开始,拷贝到nums1数组中,从下标0位置开始,长度为len2+1
        System.arraycopy(nums2, 0, nums1, 0, len2 + 1);
    }
}

时间复杂度: O(m+n)文章来源地址https://www.toymoban.com/news/detail-799851.html

到了这里,关于合并两个有序数组(简单)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法leetcode|88. 合并两个有序数组(rust重拳出击)

    给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2 ,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。 请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。 注意 :最终,合并后数组不应由函数返回,而是存储在数组 nums1 中。为了应对这种情况

    2024年02月05日
    浏览(48)
  • 【数据结构】--oj_合并两个有序链表(详解)

    目录 方法一:无头结点的方法  方法二:有头结点的方法 题述: 已给函数头: struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) 已给出链表的结构体定义: struct ListNode {     struct ListNode* next;     int val; }; 已知l1、l2分别指向两个链表 要求: 将两个升序链表合并为一

    2024年02月07日
    浏览(56)
  • 将两个递增的有序链表合并为一个递增的有序链表.【数据结构】【线性表】

    编写一个函数完成如下功能:将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来的链表空间,不另外占用其他的存储空间。表中不允许有重复的数据。 要求,在主函数中调用上面的函数测试。 提示:还需要定义其他函数,比如初始化链表,构造单

    2024年02月06日
    浏览(47)
  • 力扣_数组26—合并两个有序数组

    给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。 请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。 注意:最终,合并后数组不应由函数返回,而是存储在数组 nums1 中。为了应对这种情况,

    2024年01月21日
    浏览(43)
  • 【面试经典150 | 数组】合并两个有序数组

    本专栏专注于分析与讲解【面试经典150】算法,两到三天更新一篇文章,欢迎催更…… 专栏内容以分析题目为主,并附带一些对于本题涉及到的数据结构等内容进行回顾与总结,文章结构大致如下,部分内容会有增删: Tag:介绍本题牵涉到的知识点、数据结构; 题目来源:

    2024年02月09日
    浏览(45)
  • LeetCode 0088. 合并两个有序数组

    力扣题目链接:https://leetcode.cn/problems/merge-sorted-array/ 给你两个按 非递减顺序 排列的整数数组  nums1 和 nums2 ,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。 请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。 注意: 最终,合并后数组不应由

    2024年02月13日
    浏览(55)
  • leetcode 88 合并两个有序数组

    题目描述: 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。 请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。 注意:最终,合并后数组不应由函数返回,而是存储在数组 nums1 中。为了应

    2024年02月03日
    浏览(46)
  • Leetcode. 88合并两个有序数组

    合并两个有序数组 核心思路: 依次比较,取较小值放入新数组中 i 遍历nums1 , j 遍历nums2 ,取较小值放入nums3中 那如果nums[i] 和nums[j]中相等,随便放一个到nums3 那如果nums[i] 和nums[j]中相等,随便放一个到nums3 此时 nums1 中的元素已经走完了,那么直接把 nums2 中剩下的元素拿到

    2023年04月08日
    浏览(99)
  • LeetCode88——合并两个有序数组

    给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。 请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。 注意:最终,合并后数组不应由函数返回,而是存储在数组 nums1 中。 为了应对这种情况

    2024年02月08日
    浏览(41)
  • 【Leetcode】88.合并两个有序数组

    给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2 ,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。 请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。 注意 :最终,合并后数组不应由函数返回,而是存储在数组 nums1 中。为了应对这种情况

    2024年02月12日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包