首页 > 试题广场 >

合并两个有序的数组

[编程题]合并两个有序的数组

热度指数：261111 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给出一个有序的整数数组 A 和有序的整数数组 B ，请将数组 B 合并到数组 A 中，变成一个有序的升序数组

数据范围： $0 \le n,m \le 100$ ， $|A_i| <=100$ ， $|B_i| <= 100$

注意：
1.保证 A 数组有足够的空间存放 B 数组的元素， A 和 B 中初始的元素数目分别为 m 和 n，A的数组空间大小为 m+n

2.不要返回合并的数组，将数组 B 的数据合并到 A 里面就好了，且后台会自动将合并后的数组 A 的内容打印出来，所以也不需要自己打印

3. A 数组在[0,m-1]的范围也是有序的

示例1

输入

[4,5,6],[1,2,3]

输出

[1,2,3,4,5,6]

说明

A数组为[4,5,6]，B数组为[1,2,3]，后台程序会预先将A扩容为[4,5,6,0,0,0]，B还是为[1,2,3]，m=3，n=3，传入到函数merge里面，然后请同学完成merge函数，将B的数据合并A里面，最后后台程序输出A数组

示例2

输入

[1,2,3],[2,5,6]

输出

[1,2,2,3,5,6]

算法知识视频讲解

查看答案及解析

黄色变白色

从A和B数组的尾端开始比较，逐一把大数插入A数组，用三个坐标值记住位置

class Solution {
public:
    void merge(int A[], int m, int B[], int n) {
        if(n <= 0)
            return;
        
        int pa = m -1,pb = n -1,pc = m+n-1;
        
        while(pa >= 0 && pb >= 0)
        {
            if(A[pa] >= B[pb])
            {
                A[pc] = A[pa];
                pc = pc - 1;
                pa = pa - 1;
            }
            else
            {
                A[pc] = B[pb];
                pc = pc - 1;
                pb = pb - 1;
            }
        }
        
        while(pb >= 0 && pc >= 0)
        {
            A[pc--] = B[pb--];
        }
        
        return ;
    }
};

发表于 2020-09-04 11:39:08 回复(0)

更多回答

Butterfliesflyaway↘

public class Solution {
    public void merge(int A[], int m, int B[], int n) {
        int pa = m-1; //定义pa指向A数组末尾元素位置
        int pb = n-1; //定义pb指向B数组末尾元素位置
        int index = m+n-1; //定义index指向合并后数组（共m+n个元素）的末尾元素位置
        while(pa>=0 && pb>=0) { //A与B中都有元素时，通过上面定义的三个指针，遍历、比较大小并赋值
            if(A[pa] < B[pb]) {
                A[index] = B[pb];
                pb--;
            } else {
                A[index] = A[pa];
                pa--;
            }
            index--;
        }
        while(pb>=0) { //B中还有元素未存入A，将剩余B中的元素依次拷入A中
            A[index] = B[pb];
            pb--;
            index--;
        }
    }
}

发表于 2019-01-04 10:33:48 回复(0)

C/C++

F-L

class Solution {
public:
    void merge(int A[], int m, int B[], int n) {
        int cur = m+n-1;
        int i = m-1;
        int j = n-1;
        while(i >= 0 && j >= 0){
            if(A[i] < B[j]){
                A[cur--] = B[j--];
            }else{
                A[cur--] = A[i--];
            }
        }
        
        while(j >= 0)A[cur--] = B[j--];
    }
};

发表于 2018-03-31 15:17:38 回复(0)

sky_

//倒着归并排序
class Solution {
public:
    void merge(int A[], int m, int B[], int n) {
         int a=m-1,b=n-1,index=m+n-1;
         while(index>=0){
               if(a<0||b<0) A[index--]=a<0?B[b--]:A[a--];
               else A[index--]=A[a]<B[b]?B[b--]:A[a--];
         }
    }
};

发表于 2017-07-31 09:33:15 回复(0)

whisky_

class Solution {

public:

void merge(int A[], int m, int B[], int n) {

int *cur=A+(m--)+(n--)-1;

while(m>=0&&n>=0)

A[m]>B[n]?*(cur--)=A[m--]:*(cur--)=B[n--];

while(m>=0)

*(cur--)=A[m--];

while(n>=0)

*(cur--)=B[n--];

}

};

发表于 2017-04-04 15:09:20 回复(0)

同桌冋宇

public class Solution {
    public void merge(int A[], int m, int B[], int n)
    {
        int[] t = new int[m+n];
        int i = 0, j = 0;
        while(i < m && j < n)
        {
            if(A[i] < B[j])
            {
                t[i+j] = A[i];
                i++;
            }
            else
            {
                t[i+j] = B[j];
                j++;
            }
        }
        if(i == m)
        {
            for(; j < n; j++)
            {
                t[i+j] = B[j];
            }
        }
        else if(j == n)
        {
            for(; i < m; i++)
            {
                t[i+j] = A[i];
            }
        }
        //A = t;      //  不能简单地将一个数组赋值给另一个数组
        System.arraycopy(t, 0, A, 0, m+n);

    }
}

发表于 2016-11-19 13:48:32 回复(0)

C++

小龙20190613115478

//一行解决

while(n) A[m + n] = m && A[m - 1] > B[n - 1] ? A[--m] : B[--n];

发表于 2021-09-06 00:09:21 回复(0)

Java

华科平凡

Java三行解法

解析：这道题，要原地排序，并且不用返回结果。所以将nums2里的值一个一个的加进nums1里，再排序即可。

import java.util.Arrays;
public class Solution {
    public void merge(int A[], int m, int B[], int n) {
        for (int i = 0; i < n; i++)
            A[m + i] = B[i];
        Arrays.sort(A);
    }
}

编辑于 2018-07-04 09:33:40 回复(4)

JacobGo！

/*
	 * 最优解：从后往前处理,不需要开辟额外空间
	 * Runtime: 0 ms.Your runtime beats 45.38 % of java submissions.
	 */
	public void merge(int[] nums1, int m, int[] nums2, int n) {
		int i = m - 1, j = n - 1, index = m + n - 1;
		while (i >= 0 && j >= 0)
			nums1[index--] = nums1[i] > nums2[j] ? nums1[i--] : nums2[j--];
		while (j >= 0)
			nums1[index--] = nums2[j--];
	}

编辑于 2017-07-03 10:25:50 回复(23)

菜鸟四号

class Solution {
public:
    void merge(int A[], int m, int B[], int n) {
        for(int i=0;i<n;i++)
            A[m+i]=B[i];
        sort(A,A+m+n);
    }
};

发表于 2017-08-11 20:03:00 回复(9)

别看我只是一只羊

/*
i从A的末尾，j从B末尾开始，两两比较，大的放在末端。
比如A[4,5,7] B[1,2,6],。
7比6大，A[5]处放置7，然后i前移。
再次比较5 和6,6放在A[4]处。
如此类推如果A穷尽，把B元素依次放进A的前几个位置，如果B穷尽，正好结束。
*/
public class Solution {
    public void merge(int A[], int m, int B[], int n) {
        if(m==0){
            for(int k=0;k<B.length;k++)
                A[k]=B[k];
        }
        else{
                int i=m-1;
        	int j=n-1;
        	int s=m+n-1;
        	while(j>=0&&i>=0){
            	if(A[i]>B[j])
                	A[s--]=A[i--];
            	else
                    A[s--]=B[j--];
        		}
            if(i==-1){
                for(;j>=0;j--)
                    A[j]=B[j];
        	} 
        }
       
    }
}

编辑于 2016-05-25 17:17:52 回复(0)

牛客3857197号

//归并排序的思想，只不过这里按照题目的意思不要申请额外的空间。
//把A后面剩余的空间当额外空间。
//这里和剑指offer上的面试题5，替换空格思想一样，从后面开始往前放就可以避免大量移动
//那后面从哪里开始呢？A长m，B长n，两个合并完之后必定长m+n，所在A的A[m+n-1]开始往前放

class Solution {
public:
    void merge(int A[], int m, int B[], int n) {
        int i=m-1,j=n-1;
        int k=m+n-1;
        while(i>=0 && j>=0)
        {
            if(A[i]>B[j]) A[k--]=A[i--];
            else A[k--]=B[j--];
        }
        while(i>=0)
        {
             A[k--]=A[i--];
        }
        while(j>=0)
        {
            A[k--]=B[j--];
        }
        
    }
    
};

发表于 2018-03-19 21:35:46 回复(1)

C/C++

卷积神经网络哦

这就是归并排序中合拼的部分
由于不让new新数组(会爆)
所以将大的放在A数组的最右边从右边往左边放

class Solution {
public:

  void merge(int A[], int m, int B[], int n) {
        int i = m - 1, j = n - 1, cnt = m + n - 1;
        while(i >= 0 || j >= 0){
            if( (i >= 0 && A[i] >= B[j]) || j < 0){A[cnt--] = A[i--];}
            else {A[cnt--] = B[j--];}
        }
    }
};

发表于 2019-03-25 17:31:18 回复(1)

Java

Mono_Chrome

public class Solution {
    public void merge(int A[], int m, int B[], int n) {
        int p1 = m - 1;
        int p2 = n - 1;
        int index = m + n - 1;
        while (p1 >= 0 && p2 >= 0) {
            A[index--] = A[p1] > B[p2] ? A[p1--] : B[p2--];
        }
        while (p2 >= 0) {
            A[index--] = B[p2--];
        }
    }
}

发表于 2021-05-29 15:16:22 回复(0)

NatsumeZhang

/**
* 写在前面，题目要求的是将有序数组合并，那么有可能这所谓的有序是顺序或者逆序
* 所以，应该在开始的时候判断一下
* 然后，在比较的时候应该根据顺序逆序来写判断逻辑
* 不过常规应该是顺序递增，然后就有了以下的代码😁
*/
public void merge(int A[], int m, int B[], int n) {
        // 当n为0时，不需要合并
        if(n == 0){
            return;
        }
        // 当m为0时，并且n不为0，需要将B拷贝到A
        else if(m == 0){
            for(int i = 0 ;i < n ; i ++){
                A[i] = B[i];
            }
            return;
        }

        // 当两个数组都为0，不做操作
        if(m ==0 && n ==0){
            return;
        }

        // 分别记录A,B的最右边位置
        int i = m-1;
        int j = n-1;
        // A,B合并后的数组的角标
        int index = m + n -1;
        // B数组数据取完为结束信号
        while(j >= 0){
            // A数组还未取完
            if(i >=0){
                if(A[i]>B[j]){
                    A[index] = A[i];
                    i--;
                }else{
                    A[index] = B[j];
                    j--;
                }
            }
            // A数组已取完，将B逆序添加到A后
            else{
                A[index] = B[j];
                j--;
            }
            
            // 每次添加一个数进去，指针就向前移
            index --;
        }
    }

发表于 2020-12-27 12:04:08 回复(1)

chorifa

// 归并后的整个数组长度是已知的，从后往前可以避免移位
// 数组默认是从小到大的
public class Solution {
    public void merge(int A[], int m, int B[], int n) {
        int i = m-1, j = n-1;
        while(i>=0 && j>=0)
            A[i+j+1] = A[i]>B[j]?A[i--]:B[j--];
        while(j>=0) A[j] = B[j--]; // 只需要考虑B尚未空的情况
    }
}

发表于 2018-12-18 15:22:49 回复(0)

_liu_

由于惯性思维，我们很容易想到从头开始比较两个数组，然后将小的数存到数组A中，但是存在一个问题，当数组B中的数连续多个数都比A中同一个数小时，那么将B中的数放到A中就会覆盖A中的数！

因此，我们换个思维思考一下，因为数组A和数组B的长度已经确定，那么构建的新数组的长度就已经确定了，我们可以从后面的数开始比较，将A和B中的数从后向前比较，谁大就将大的数放到新A数组的后面，这样既方便了遍历又解决了从头遍历到尾的问题。

注释如下：

发表于 2020-10-30 22:54:28 回复(1)

Java

牛客612045000号

public void merge(int A[], int m, int B[], int n) {
        if(A == null || B == null){
            return ;
        }
        for(int i = m,j = 0;i<A.length && j<n;i++,j++){
           A[i] = B[j];
        }
        Arrays.sort(A);
}

发表于 2022-08-03 17:37:03 回复(0)

Java

雷欧尼桑

import java.util.Arrays;

public class Solution {
    public void merge(int A[], int m, int B[], int n) {
        for (int i = m; i < m + n; i ++) {
            A[i] = B[i - m];
        }
        Arrays.sort(A);
    }
    
}

发表于 2021-08-14 14:27:31 回复(2)

midiya

/**
 * 
 * @param A int整型一维数组 
 * @param ALen int A数组长度
 * @param B int整型一维数组 
 * @param BLen int B数组长度
 * @return void
 */
void merge(int* A, int ALen, int m, int* B, int BLen, int n) {
    int i=ALen-1,j=BLen-1,index=ALen+BLen-1;
    while(i>=0 && j>=0) {
        
        if(A[i]>B[j]) {
            A[index--] = A[i--];
        }else {
            A[index--] = B[j--];
        }

    }
    while(j>=0) {
        A[index--] = B[j--];
    }
    
}

编辑于 2021-07-18 20:28:11 回复(0)

hearlistenting

import java.util.*;
public class Solution {
    public void merge(int A[], int m, int B[], int n) {
       for(int i=0;i<n;i++){
           A[m+i]=B[i];
       }
        Arrays.sort(A);
        
    }
}

Try that

发表于 2020-09-26 13:06:46 回复(0)

提交观点

问题信息

数组双指针

难度：

492条回答 927收藏 32562浏览

通过挑战的用户

查看代码

大胆的猪猪在午休

2023-03-03 16:07:39
牛客47096...

2023-02-09 15:35:27
牛客43914...

2023-02-06 21:56:34
UKen

2023-01-15 21:56:28
JimSu

2023-01-13 08:49:17

合并两个有序的数组

输入

输出

说明

输入

输出

Java三行解法

问题信息

热门推荐

通过挑战的用户

相关试题