两个有序数组合并成一个有序数组

冷不防 2022-08-06 02:11 251阅读 0赞

**两个有序数组合并成一个有序数组**

# 1. 题目描述  #

数组a是有序的，数组b也是有序的，如何高效地合并它们成一个数组，并且新数组也是有序的？

# 2. 从后往前合并 #

这道题目是师兄电面阿里的时候，问到的一道题目。现在我们来说一下解法~

假设数组a足够长，可以在数组a上合并二者。我们的解法基本思想就是从后往前合并数组。

每次合并的时候，都要比较a和b当前数组的大小，取较大的值后移，注意一定要是后移！

为什么从后往前呢？其实就是为了方便后移，因为较大的一定是在后面的。

程序如下：

#include<iostream>
    using namespace std; 
    #define MAX 100
    int main()
    {
    	int a[MAX]={1,3,5,7,9}; 
    	int b[MAX]={2,4,6,8}; 
    	int len1=5, len2=4; 
    
    	int p1=len1-1, p2=len2-1;  //从后往前遍历
    	int q=len1+len2-1; 
    
    	while(p1>=0 && p2>=0)  //二者长度相等部分
    	{
    		if(a[p1]>=b[p2])
    		{
    			a[q]=a[p1]; 
    			p1--; 
    			q--; 
    		}
    		else
    		{
    			a[q]=b[p2]; 
    			q--; 
    			p2--; 
    		}
    	}
    
    	while(p1>=0)  //假如a数组多出来
    	{
    		a[q]=a[p1]; 
    		q--; 
    		p1--; 
    	}
    
    	while(p2>=0)  //假如b数组多出来
    	{
    		a[q]=b[p2]; 
    		q--; 
    		p2--; 
    	}
    
    	for(int i=0; i<len1+len2-1; i++)
    		cout<<a[i]<<' '; 
    	cout<<endl;
    	
    	return 0; 
    }

结果：

![Center][]

[Center]: /images/20220806/4c6b0b1c9ce64657bff9cb5fc6c64926.png

发表评论取消回复

表情：

评论列表（有 0 条评论，251人围观）

还没有评论，来说两句吧...

相关阅读

相关合并两个有序数组

合并两个有序数组 1、参考资料 https://leetcode-cn.com/problems/merge-sorted-array/ 2、题目要求 >

绝地灬酷狼/ 2022年12月08日 05:15/ 0 赞/ 240 阅读

相关两个或多个有序数组合并为一个有序数组

要求：不使用for循环不使用API方法进行数据迁移： System.arraycopy(int\[\] a,…); Arrays.copyOf(int\[

「爱情、让人受尽委屈。」/ 2022年09月16日 12:20/ 0 赞/ 223 阅读

相关两个有序数组合并成一个有序数组

两个有序数组合并成一个有序数组 1. 题目描述数组a是有序的，数组b也是有序的，如何高效地合并它们成一个数组，并且新数组也是有序的？ 2.

冷不防/ 2022年08月06日 02:11/ 0 赞/ 252 阅读

相关两个有序数组合并成一个有序数组

思想：先依次比较两个数组，按照小的就传入新的数组。当这次比较完之后可能有一个数组的长度很长，留下一些数组，然后在新数组的末尾插入即可。代码： pub

亦凉/ 2022年08月04日 08:39/ 0 赞/ 296 阅读

相关 1124: 两个有序数组合并

Description 已知数组a中有m个按升序序排列的元素，数组b中有n个降序排列的元素，编程将a与b中的所有元素按降序存入数组c中。 Input 输入有两行，

柔情只为你懂/ 2022年06月12日 14:08/ 0 赞/ 260 阅读

相关合并两个有序数组

给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。说明: 初始化 nums1 和 nums2 的

╰半夏微凉°/ 2022年04月16日 06:11/ 0 赞/ 307 阅读

相关 88、合并两个有序数组

给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。说明: 初始化 nums1 和 nums2 的

深藏阁楼爱情的钟/ 2022年02月21日 12:11/ 0 赞/ 314 阅读

相关 LeetCode----------------------合并两个有序数组

给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。说明: 初始化 nums1 和 nums2 的

爱被打了一巴掌/ 2021年12月10日 00:39/ 0 赞/ 362 阅读

相关合并两个有序数组

给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。说明: 初始化 nums1 和 nums2

一时失言乱红尘/ 2021年11月16日 12:52/ 0 赞/ 387 阅读

相关 88、合并两个有序数组

给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。说明: 初始化 nums1 和 nums

﹏ヽ暗。殇╰゛Y/ 2021年11月01日 15:26/ 0 赞/ 454 阅读