首页 > 试题广场 >

合并两个有序的数组

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

热度指数：255961 时间限制：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]

算法知识视频讲解

查看答案及解析

Java

C语言学者初来乍到

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

发表于 2023-11-22 23:46:16 回复(0)

Java

BlueProtocol

容易理解的

public class Solution {
    public void merge(int A[], int m, int B[], int n) {
        //如果不能开辟空间，已经指定一个数组有足够的空间了，那么
        //我们可以从后面开始修改，从后面开始遍历，从大的开始
        if (m == 0 && n == 0) return;
        int index = m + n - 1;
        int i = m - 1;
        int j = n - 1;
        while (i >= 0 && j >= 0) {
            if (A[i] < B[j])   A[index--] = B[j--];
            else    A[index--] = A[i--];
        }
        if (i < 0) {
            while (j >= 0) {
                A[index--] = B[j--];
            }
        }
        return;
    }
}

发表于 2023-11-05 00:20:46 回复(0)

Java

求知心态

import java.util.*;
public class Solution {
    public void merge(int A[], int m, int B[], int n) {
        int i = m - 1;
        int 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 (j >= 0) {
            A[k--] = B[j--];
        }
    }
}

发表于 2023-10-23 10:44:26 回复(0)

Java

roses_are_roses

不讲武德：

1.排序

2.冒泡

走你

发表于 2023-08-07 15:51:43 回复(0)

Java

牛客101757813号

public void merge(int A[], int m, int B[], int n) {
        for (int i = m, j = 0 ; i < m + n && j < n ; i++, j++) {
            A[i] = B[j];
        }
        for (int i = 0 ; i < A.length ; i++) {
            for (int j = 0 ; j < A.length - 1 - i ; j++) {
                if (A[j] > A[j + 1]) {
                    int temp = A[j];
                    A[j] = A[j + 1];
                    A[j + 1] = temp;
                }
            }
        }
    }

发表于 2023-08-02 20:10:36 回复(1)

Java

梁山教父

import java.util.*;
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);
    }
}

发表于 2023-06-25 09:19:11 回复(1)

Java

做则必成的勇气和信心

import java.util.*;
public class Solution {
    public void merge(int A[], int m, int B[], int n) {
        int p1=m-1;
        int p2=n-1;
        int ppp=m+n-1;
        int cur;
        while(p1>=0||p2>=0){
            if(p1==-1){
                cur=B[p2--];
            }else if(p2==-1){
                cur=A[p1--];
            }else if(A[p1]>B[p2]){
                cur=A[p1--];
            }else{
                cur=B[p2--];
            }
            A[ppp--]=cur;
        }
    }
}

发表于 2023-05-03 21:22:59 回复(0)

Java

上将军邢道荣

import java.util.*;
public class Solution {
    public void merge(int A[], int m, int B[], int n) {
       int t=0;
        while (m != 0 && n != 0) {
            t = m + n - 1;
            if (A[m - 1] > B[n - 1]) {
                A[t] = A[m - 1];
                m--;
            } else {
                A[t] = B[n - 1];
                n--;
            }
        }
        t=m+n-1;
        if (m == 0 && n != 0) {
            while (n != 0) {
                A[t] = B[n - 1];
                n--;
                t--;
            }
        }
        if (n == 0 && m != 0) {
            while (m != 0) {
                A[t] = A[m - 1];
                m--;
                t--;
            }
        }
    }
}

nice

发表于 2023-04-28 02:40:30 回复(0)

Java

35岁打螺丝转Java

//不讲武德解法

import java.util.*;

public class Solution {

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

int index = m;

int c = 0;

for(int i = index;i < n + m;i++){

A[i] = B[c];

c++;

}

Arrays.sort(A);

}

发表于 2023-04-10 21:43:14 回复(1)

Java

一剑飘红2021

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

发表于 2023-02-04 15:42:47 回复(0)

Java

肥咩咪

类似于归并排序中的合并过程

import java.util.*;
public class Solution {
    public void merge(int A[], int m, int B[], int n) {
        if(A==null||B==null||A.length==0||B.length==0){
            return;
        }

        int l=0;
        int r=0;
        int tempIndex=0;
        int[] tempArr=new int[m+n];

        while(l<m&&r<n){
            if(A[l]<=B[r]){
                tempArr[tempIndex]=A[l];
                l++;                      
            }else{
                tempArr[tempIndex]=B[r];
                r++;
            }
            tempIndex++;
        }

        while(l<m){
            tempArr[tempIndex]=A[l];
            l++;
            tempIndex++;
        }

        while(r<n){
            tempArr[tempIndex]=B[r];
            r++;
            tempIndex++;
        }
       for(int i=0;i<m+n;i++){//注意这里是m+n,m+n才是数组A的长度，而m只是有效的元素个数
           A[i]=tempArr[i];
       }
        
    }
}

发表于 2022-10-01 20:22:19 回复(0)

Java

624huiguorou

从后往前遍历，不断的取两个数组中的较大值即可

A数组的长度为A+B的长度，A后面都是0。

import java.util.*;
public class Solution {
    //之所以从后往前，是利用元素有序
    public void merge(int A[], int m, int B[], int n) {
        int i = m - 1, j = n - 1, k = m + n - 1;
        while (j >= 0) {
            if (i < 0 || B[j] > A[i]) {
                A[k--] = B[j--];
            } else {
                A[k--] = A[i--];
            }
        }
    }
}

发表于 2022-09-19 18:14:54 回复(0)

Java

offer多多_益_善

/**

从后往前来进行比较是比较好做的，相对比较容易，代码很简洁，和归并排序的那个代码差不多

import java.util.*;

public class Solution {
public void merge(int A[], int m, int B[], int n) {
int i = m-1;
int j = n-1;
int k = A.length - 1;
for (; 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--];
}
}
}

发表于 2022-09-08 13:54:57 回复(0)

Java

已注销

import java.util.*;
public class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int n1 = 0,n2 = 0;
        int[] temp = new int[n+m];
        for(int i = 0;i<m+n;i++){
            if(n1<m&&n2<n){
                if(nums1[n1]<nums2[n2]){
                    temp[i] = nums1[n1++];
                }else{
                    temp[i] = nums2[n2++];
                }
            }else{
                if(n2<n){
                    temp[i] = nums2[n2++];
                }
                if(n1<m){
                    temp[i] = nums1[n1++];
                }
            }
        }
        for(int k = 0;k<n+m;k++){
            nums1[k] = temp[k];
        }
    }
}

发表于 2022-08-22 12:25:56 回复(0)

Java

牛客226864759号

public void merge(int A[], int m, int B[], int n) {
        while(n-1>=0){
            A[m+n-1] = (m-1<0||A[m-1]<=B[n-1])?B[--n]:A[--m];
        }
    }

发表于 2022-08-07 16:04:45 回复(0)

Java

lizi-hust

import java.util.*;
public class Solution {
    public void merge(int A[], int m, int B[], int n) {
        int p1 = m-1;
        int p2 = n-1;
        while(p1>=0 && p2>=0){
            if(A[p1]>B[p2]) A[p1+p2+1] = A[p1--];
            else A[p1+p2+1] = B[p2--];
        }
        while(p2>=0){
            A[p2] = B[p2--];
        }
    }
}

发表于 2022-08-07 14:58:45 回复(0)

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

牛客598099835号

import java.util.*;
public class Solution {
    public void merge(int A[], int m, int B[], int n) {
        int i = m - 1;
        int j = 0;
        while (j < B.length) {
            while (i >= 0 && A[i] > B[j]) {
                A[i+1] = A[i];
                i--;
            }
            A[i+1] = B[j];
            j++;
            i = m - 1 + j;
        }
    }
}

发表于 2022-08-02 23:23:26 回复(0)