C语言每日一题(22)合并两个有序数组

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

力扣网 88. 合并两个有序数组

题目描述

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。

注意:最终,合并后数组不应由函数返回,而是存储在数组 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 中。

思路分析

方法1

时间复杂度  O(m+n)

空间复制度 O(m+n)

这是最基本的思路,将两个数组从头遍历,分别比较大小,较小的值先放到一个新创建的数组里,比较完后可能会存在剩余的情况,再将剩余的值放入新数组,题目要求返回数组1,再将新数组的内容拷贝进数组1里即可

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){

    int s1=0;

    int s2=0;

    int num3[200]={0};//新数组

    int i=0;

    while(s1<m&&s2<n)//任何一个数组遍历完结束循环

    {

        if(nums1[s1]<nums2[s2])//较小值先放

        {

            num3[i++]=nums1[s1++];

        }

        else if(nums1[s1]==nums2[s2])//相等则一起放,任意规则

        {

            num3[i++]=nums1[s1++];

            num3[i++]=nums2[s2++];

        }

        else

        {

            num3[i++]=nums2[s2++];

        }

    }

    if(s1==m)//s1遍历完的情况下,s2还没有遍历完的情况下

    {

        while(s2<n)

        {

            num3[i++]=nums2[s2++];

        }

    }

    if(s2==n)//s2遍历完的情况下,s1还没有遍历完

    {

        while(s1<m)

        {

            num3[i++]=nums1[s1++];

        }

    }

    for(int j=0;j<nums1Size;j++)//将新数组拷贝到数组1里

    {

        nums1[j]=num3[j];

    }



}

方法2

时间复杂度  O(m+n)

空间复杂度  O(1)

思路:从两个数组的末尾开始遍历,数组1从最后一个数开始向前遍历,较大值放到数组1的末尾,如果遍历完数组2还有剩余的话直接放入。

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
    int s1=m-1;//数组1的末尾(最后一个数字)
    int s2=n-1;//数组2的末尾
    int index=m+n-1;//(数组1的末尾)
    while(s1>=0&&s2>=0)
    {
        if(nums1[s1]>nums2[s2])
        {
            nums1[index--]=nums1[s1--];
        }
        else
        {
            nums1[index--]=nums2[s2--];
        }
    }
    while(s2>=0)//数组2还有剩余的情况
    {
        nums1[index--]=nums2[s2--];
    }

}

 文章来源地址https://www.toymoban.com/news/detail-714615.html

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

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

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

相关文章

  • 2023-08-13 LeetCode每日一题(合并两个有序数组)

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

    2024年02月13日
    浏览(59)
  • 【力扣每日一题】88. 合并两个有序数组 &双指针 & 辅助数组 & 8.13打卡

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

    2024年02月09日
    浏览(40)
  • 【每日算法 && 数据结构(C++)】—— 03 | 合并两个有序数组(解题思路、流程图、代码片段)

    An inch of time is an inch of gold, but you can’t buy that inch of time with an inch of gold. An inch of time is an inch of gold, but you can\\\'t buy that inch of time with an inch of gold 给你两个有序数组,请将两个数组进行合并,并且合并后的数组也必须有序 这个题目要求将两个有序数组合并成一个有序数组。在数

    2024年02月11日
    浏览(53)
  • 数据结构c语言版:顺序表oj题练习(原地移除元素、合并两个有序数组)

    在单数组里面历遍找val,如果是val,就删除。不是就跳过。 时间复杂度O(n^2),最坏情况每个都是val。相当于一个等差数列。 比如 下标0开始找,0不是,不动数组 下标1,1不是,不动数组 下标2,2是,删除元素,变成【0,1,2,3,0,4,2】 下标2,2是,删除元素,变成【0,

    2024年01月23日
    浏览(63)
  • 力扣经典150题第一题:合并两个有序数组

    合并两个有序数组问题详解与解决方法 1. 介绍 在编程面试中,合并两个有序数组是一个经典的问题。它要求将两个有序数组合并为一个新的有序数组。本篇博客将深入讨论这个问题,并提供解决方法。 2. 问题描述 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两

    2024年04月23日
    浏览(41)
  • “三指针法“合并两个有序数组(力扣每日一练)

            我的第一想法确实是:先合并数组,再排序,搞完。         哈哈哈,想那么多干嘛,目的达成了就好了。 力扣官方题解是双指针: 还有糕手: Python: C#:       总结         可以称之为\\\"三指针\\\" 方法,因为我们同时使用了三个指针(p1、p2 和 p)来操作和遍历两

    2024年02月02日
    浏览(41)
  • 力扣每日一道系列 --- LeetCode 88. 合并两个有序数组

    📷 江池俊: 个人主页 🔥个人专栏: ✅数据结构探索 ✅LeetCode每日一道 🌅 有航道的人,再渺小也不会迷途。 LeetCode 88. 合并两个有序数组 首先创建一个临时数组,其大小为第一个数组的大小(即nums1Size),其作用主要是。 通过循环遍历两个数组,将两个数组元素比较后较

    2024年02月04日
    浏览(48)
  • C语言每日一题:5.至少是其他数字的两倍+两个数组的交集。

    第一题: 1.需要我们返回最大数值的下标,所以先循环遍历我们的这个数组记录一下最大的数值和下标位置。 2.使用qsort排序(总是存在唯一的最大整数) 3所以排序之后的数组的倒数第二个元素就是除了最后一个元素在数组中最大的。 4.只需要判断这个数的两倍是否小于等于

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

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

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

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

    2024年02月09日
    浏览(45)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包