首页 > 试题广场 >

合并两个有序的数组

[编程题]合并两个有序的数组
  • 热度指数：256064 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给出一个有序的整数数组 A 和有序的整数数组 B ，请将数组 B 合并到数组 A 中，变成一个有序的升序数组

数据范围： ，，

注意：
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]
算法知识视频讲解
添加回答
Java
牛客612045000号头像 牛客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)
C++
牛客嗷嗷头像 牛客嗷嗷 
class Solution
{
public:
    void merge(int A[], int m, int B[], int n)
    {
        int index = m + n;
        while (m && n)
            A[--index] = (A[m - 1] > B[n - 1] ? A[--m] : B[--n]);
        while (n)
            A[--index] = B[--n];
    }
};

发表于 2022-02-23 17:36:27 回复(0)
给我offer我要offer头像 给我offer我要offer 
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);
    }
}

发表于 2020-08-29 18:40:53 回复(1)
Butterfliesflyaway↘头像 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头像 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_头像 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_头像 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)
T+T头像 T+T 
public void merge(int A[], int m, int B[], int n) {
        int i=0,j=0;
        while (i<m&&j<n){
          if (A[i]<=B[j]){
              i++;
          }else {
              for (int x=m;x>i;x-- ){
                    A[x]=A[x-1];
              }
              A[i++]=B[j++];
              m++;
          }
        }
        while (i>=m&&j<n){
            A[i++]=B[j++];
        }
    }

发表于 2017-04-01 17:39:43 回复(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)
xiao_lai头像 xiao_lai 
class Solution {
public:
    void merge(int A[], int m, int B[], int n) {
        //You may assume that A has enough space to hold additional elements from B
        int size = m+n;
        //这里需注意空数组的判读，否则后面会数组越界
        if(n==0)return;
        if(m==0){
            for(int i=0;i<n;i++){
                A[i]=B[i];
            }
            return;
        }
        int aIndex=m-1,bIndex=n-1;
        for(int i=size-1;i>=0;i--){ //类似于归并排序最后的合并操作
            if(A[aIndex]>B[bIndex]){
                A[i]=A[aIndex--];
            }else{
                A[i]=B[bIndex--];
            }
            if(aIndex<0){
                while(--i>=0){
                    A[i]=B[bIndex--];
                }
                break;
            }
            if(bIndex<0){
                break;                
            }
        }
    }
};

发表于 2016-06-26 22:44:55 回复(0)
C++
小龙20190613115478头像 小龙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！头像 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号头像 牛客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头像 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头像 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头像 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)
提交观点

问题信息

数组 双指针
难度：
484条回答 30777浏览

热门推荐

通过挑战的用户

相关试题

合并两个有序的数组

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号