首页 > 试题广场 >

合并两个有序的数组

[编程题]合并两个有序的数组
  • 热度指数:255938 时间限制: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]
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)
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)
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)
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)
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)
//倒着归并排序
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)
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)
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)
//一行解决 
while(n) A[m + n] = m && A[m - 1] > B[n - 1] ? A[--m] : B[--n];
发表于 2021-09-06 00:09:21 回复(0)

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)
/*
	 * 最优解:从后往前处理,不需要开辟额外空间
	 * 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)
//归并排序的思想,只不过这里按照题目的意思不要申请额外的空间。
//把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)

这就是归并排序中合拼的部分
由于不让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)
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)
/**
* 写在前面,题目要求的是将有序数组合并,那么有可能这所谓的有序是顺序或者逆序
* 所以,应该在开始的时候判断一下
* 然后,在比较的时候应该根据顺序逆序来写判断逻辑
* 不过常规应该是顺序递增,然后就有了以下的代码😁
*/
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)
// 归并后的整个数组长度是已知的,从后往前可以避免移位
// 数组默认是从小到大的
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)