首页 > 其他分享 >88. 合并两个有序数组

88. 合并两个有序数组

时间:2022-09-23 22:33:49浏览次数:57  
标签:数组 temp int 元素 88 有序 nums1 nums2

题目

给你两个按 非递减顺序 排列的整数数组 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 中的元素。

题解

当m=0时,将nums2[n]中的值分别赋给nums1[m+n];当n=0时,不做任何处理;当m、n不为0时,使用归并排序算法中并的部分,定义三个索引 l、r、i 和一个临时数组temp[ ];l指向nums1数组的第一个元素,r指向nums2数组的第一个元素,i指向temp数组的第一个元素;比较nums1[l]和nums2[r]的大小,将较小值放入temp[i++]中,同时l++;反之r++;当nums1或者nums2中还有剩余的数值时单独处理。注意:temp数组索引的长度

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

    int r=0,l=0 ;     int i=0,temp[200];     if(n==0) return;     if(m==0){         for(int j=0;j<n;j++)         nums1[j]=nums2[j];         return;     }     while(l<m && r<n){         temp[i++]=(nums1[l]<nums2[r])?nums1[l++]:nums2[r++];     }
    while(l<m){         temp[i++]=nums1[l++];     }     while(r<n){         temp[i++]=nums2[r++];     }     for(int j=0;j<m+n;j++)     nums1[j]=temp[j]; }   时间复杂度:O(n) 空间复杂度:O(1)

提示:

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

 

 

标签:数组,temp,int,元素,88,有序,nums1,nums2
From: https://www.cnblogs.com/lazykora/p/16724546.html

相关文章

  • python文件读取错误UnicodeDecodeError: 'utf-8' codec can't decode byte 0x92 in po
    参考:https://segmentfault.com/q/1010000004268196/a-1020000004269556ubuntu下Python3使用open('filename','r').read()读取.txt文件时抛出异常:UnicodeDecodeError......
  • 数组扁平化
    数组扁平化:多维数组变一维数组。方式1:ES6中的flat函数letarr=[1,2,3,[4,5,6,[7,9,8]]];console.log(arr.flat(Infinity));方式2:扩展运算符vararr=[1,2......
  • cC语言第16天,声明器、函数指针与数组
    一、声明器提供标识符与类型信息,用于声明一个标识符的语法被称作声明器。1.声明数组B1.元素类型:int[10];2.数组名:B;3.元素个数:5按照公式,我们写出如下形式的声明:int[10]......
  • java基础-冒泡排序以及稀疏数组
     java基础 以下内容为本人的学习笔记,如需要转载,请声明原文链接   https://www.cnblogs.com/lyh1024/p/16720908.html Ø 冒泡排序原理:比较数组中,两个相邻的元......
  • 对象数组去重(保留最后的数据)
    constarrayUnique=(arr:any,name:any)=>{varhash:any={}returnarr.reduce((acc:any,cru:any,index:any)=>{if(!hash[cru[name]]){......
  • JS 数组操作
    一、改变原数组方法  push()、pop()、shift()、unshift()、reverse()、sort()、splice() 二、数组操作方法ps:新增返回lenth,删除返回当前元素1、push()将......
  • laravel DB::select 结果转为数组
    1、select结果数组元素为对象,需要将对象转为数组,方便使用。$sql="selectid,order_code,contentfromoms_order_logwhereid<10";$data=DB::select($sql);dd......
  • 力扣21(java&python)-合并两个有序链表(简单)
    题目:将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。  示例1:输入:l1=[1,2,4],l2=[1,3,4]输出:[1......
  • 实例88 最小二乘法拟合
    #include<stdio.h>#include<stdlib.h>#include<malloc.h>#include<math.h>Smooth(double*,double*,double*,int,int,double*,double*,double*);......
  • 题解【P5588 hegm 爬树】
    题目传送门。来一个不一样的工程做法。我们直接对于每一个颜色\(i\)建虚树,显然可以通过树形DP来判断颜色\(i\)的节点是否在一条路径上。原题。然后存一下这条路径......