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

88. 合并两个有序数组

时间:2023-08-03 22:55:05浏览次数:42  
标签:数组 int 合并 88 vector 有序 nums1 nums2

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 = [0], m = 0, nums2 = [1], n = 1
输出:[1]
解释:需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意,因为 m = 0 ,所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

答案1(李煜东):

class Solution
 {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) 
    {
        vector<int> result;
        int i = 0, j = 0; 
        while(i < m || j < n)
        {
            //什么时候要nums1[i]?或者j出界,或者i,j都没出界,要小的
            if(j >= n || (i < m && nums1[i] <= nums2[j]))
            {
                result.push_back(nums1[i]);
                i++;
            }
            else
            {
                result.push_back(nums2[j]);
                j++;
            }
        }
        for(int i = 0; i < m + n; i++)  nums1[i] = result[i];
    }
};

答案2(李煜东):

class Solution
 {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) 
    {
        int i = m - 1;
        int j = n - 1;
        for(int k = m + n - 1; k>= 0; k--)
        {
            //什么时候要nums1[i]?或者j出界了,或者i,j都没出界,nums1[i]大于nums2[j]
            if(j < 0 || (i >= 0 && nums1[i] > nums2[j]))
            {
                nums1[k] = nums1[i--];
            }
            else
            {
                nums1[k] = nums2[j--];
            }
        }
    }
};

标签:数组,int,合并,88,vector,有序,nums1,nums2
From: https://www.cnblogs.com/codemagiciant/p/17604710.html

相关文章

  • 两个有序数组的中位数(第k大的数)——使用二分答案的思路写起来更直观
    问题:两个已经排好序的数组,找出两个数组合并后的中位数(如果两个数组的元素数目是偶数,返回上中位数)。 感觉这种题目挺难的,尤其是将算法完全写对。因为当初自己微软面试的时候遇到了,但是没有想出来思路。看网上写了一堆解法,但是将思路说得非常清楚的少之又少。有两种思路,一个是算法导......
  • 26. 删除有序数组中的重复项
    26.删除有序数组中的重复项![image-20230803210215410](D:\BaiduSyncdisk\C++\笔记图片\26.删除有序数组中的重复项1.png)题目:给你一个升序排列的数组nums,请你原地删除重复出现的元素,使每个元素只出现一次,返回删除后数组的新长度。元素的相对顺序应该保持一致。然后返回......
  • 剑指 Offer 04. 二维数组中的查找(中等)
    题目:classSolution{public:boolfindNumberIn2DArray(vector<vector<int>>&matrix,inttarget){inti=matrix.size()-1,j=0;//以矩阵最左下角作为标记符号while(i>=0&&j<matrix[0].size()){i......
  • shell 读取文件内容到数组
     在shell脚本中,可以使用下面的语法来读取文件内容并将其存储到数组中: bash复制代码array=()whilereadline;doarray+=("$line")done<file.txtLOG_INFO(){localcontent=${1}echo-e"\033[32m[INFO]${content}\033[0m"}IFS=''catbanner.......
  • shell 将文件内容读取到 数组中
    #!/bin/bashprod_file=/home/vmuser/linbo/kettleDemo/job/test/CA-20201224.csvtest_file=/home/vmuser/linbo/kettleDemo/job/test/uat_CA-20201224.csvdtm=`date+"%Y%m%d%H%M%S"`echo$dtmrowCnt=`cat$test_file|wc-l`echo$rowCntecho"-----......
  • 剑指 Offer 11. 旋转数组的最小数字(简单)
    题目:classSolution{public:intminArray(vector<int>&numbers){intresult=numbers[0];//当旋转0个元素时第一个元素就是最小值if(numbers.size()==1)returnresult;for(inti=1;i<numbers.size();i++){//通过观......
  • 数组双指针技巧汇总 [labuladong-刷题打卡 day2]
    https://labuladong.github.io/algo/challenge/ji-chu-tiao-zhan/day02/快慢指针26.删除有序数组中的重复项两个指针分别维护符合条件数组和待删除数组,当快指针移动时将符合条件元素插入已完成数组后即可。通过这两天对双指针的练习,可以发现很多双指针算法其实也是一种迭代算......
  • 前缀和数组技巧 [labuladong-刷题打卡 day3]
    今天是两道前缀和,主要有一维前缀和和二维前缀和,当然扩充到高维也是可以的,只不过状态转移会相对复杂些。这里直接贴一个动态规划的介绍吧:动态规划要素动态规划概念、特点、经典例题和于其它算法思想的比较前缀和其实是备忘录自底向上动态规划算法的一个典型例子,状态转移方程:一......
  • SL651数据采集实现水文实时监测,助力防汛减灾工作有序开展
    SL651协议是水文监测数据通信规约,应用于水库监测站、数据采集传输系统和提供数据监测分析服务的物联网平台。物通博联提供SL651数据采集能力的工业智能网关对接到各级监管平台,实现对江河水库流域水位、降雨量、流量、水质等数据的实时采集、报送、处理和分析,提供信息共享的透明的......
  • 树状数组
    log(n)修改,log(n)查询可以顶替掉一部分线段树的作用,而且码量十分友好但是对我来说是有点难理解的,现在只是大体理解,没有很通透,所以不写自己的理解了,以后要多看看1.单点修改区间查询https://blog.csdn.net/ls2868916989/article/details/119268741代码(P3374):#include<iostream>#i......