首页 > 试题广场 >

合并两个有序的数组

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

热度指数：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]

算法知识视频讲解

想要躺平的凉某

void merge(int* A, int ALen, int m, int* B, int BLen, int n) {

// write code here

//合并A和B

int num=ALen;

for (int j = 0; j < n; j++) {

A[num] = B[j];

num++;

}//用两个for循环可能会导致逻辑错误，直接定义一个数并在for循环里直接++就好

int temp;//冒泡函数交换中介

for(int i=0;i<m+n-1;i++){

for(int j=0;j<m+n-i-1;j++){

if(A[j]>A[j+1]){

temp=A[j];

A[j]=A[j+1];

A[j+1]=temp;

}

个人拙见

编辑于 2024-01-16 17:42:14 回复(0)

猪猪侠的飞天梦

/**
 *
 * @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) {
    // write code here
    int i = ALen - 1, j = BLen - 1, k = ALen + BLen - 1;
    while (i >= 0 && j >= 0) {

        if (A[i] >= B[j]) A[k--] = A[i--];
        else A[k--] = B[j--];
    }
    while(i < 0 && j>=0) A[k--] = B[j--];
    while(j < 0 && i>=0) A[k--] = A[i--];
}

发表于 2023-11-30 18:04:52 回复(0)

陈让然

我是笨蛋，还是大家厉害
#include <stdlib.h> void merge(int* A, int ALen, int m, int* B, int BLen, int n) { // write code here //暂时存放A数组元素 int *arr=(int*)malloc(ALen*sizeof(int)); for(int i=0;i<m;i++) { arr[i]=A[i]; } //定义双指针 int*p1=arr; int*p2=B; int count=0; //从小端开始遍历，小的元素放前面 while(p1!=&arr[m]&&p2!=&B[n]&&m>=0&&n>=0) { A[count++]=*p1>*p2?*p2++:*p1++; } //若还有未遍历完的元素，因此放入A数组后面 while(p1!=&arr[m]) { A[count++]=*p1++; } while(p2!=&B[n]) { A[count++]=*p2++; } //释放堆空间 free(arr); }

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

发表于 2023-09-16 14:29:51 回复(0)

牛客865521618号

void merge(int* A, int ALen, int m, int* B, int BLen, int n) {

// write code here

for(int j =0;j<=BLen;j++){

A[ALen+j] = B[j];

}

for(int i=0; i<ALen + BLen; i++){

for(int k=i+1; k<ALen + BLen; k++){

if(A[i] > A[k]){

int f =0;

f = A[k];

A[k]=A[i];

A[i]=f;

}

为什么存在越界非法访问的问题

发表于 2022-10-15 21:23:32 回复(1)

胡涂涂~


/*
双指针，不会浪费多余的空间
*/
void merge(int* A, int ALen, int m, int* B, int BLen, int n) {
    // write code here
    int i = m-1 ;
    int j = n-1 ;
    int k = n+m-1 ;
    int end ;
    int *p ;
    while((i>=0)&&(j>=0)){
        if(A[i] > B[j]){
            A[k] = A[i] ;
            k-- ;
            i-- ;
        }else{
            A[k] = B[j] ;
            k-- ;
            j-- ;
        }
    }
    if(i>=0){
      end = i ;
      p = A ;
    }
    else if(j>=0){
       end = j ;
       p = B ;
    }
    while(end>=0){
        A[k] = p[end] ;
        --k ;
        --end ;
    }
    ALen = m+n ;
    BLen = n ;
   
}

发表于 2022-07-04 16:21:33 回复(0)

理智的布拉德在看面经

/**
 * 
 * @param A int整型一维数组 
 * @param ALen int A数组长度
 * @param B int整型一维数组 
 * @param BLen int B数组长度
 * @return void
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
void merge(int* A, int ALen, int m, int* B, int BLen, int n) {
    // write code here
    int end1 = m-1;  //第一个数组的长度
    int end2 = n-1;  //第二个数组的长度
    int end = m+n-1; //第一个数组的总长度
    while(end1>=0 && end2>=0)
    {
        if(A[end1] > B[end2])
        {
            A[end] = A[end1];
            end--;
            end1--;
        }
        else
        {
            A[end] = B[end2];
            end--;
            end2--;
        }
    }
      while(end2>= 0)
        {
            A[end--] = B[end2--];
        }
}

发表于 2022-06-28 10:21:05 回复(0)

阿金要努力

void merge(int* A, int ALen, int m, int* B, int BLen, int n) 
{
    // write code here
    int* C=(int*)malloc(sizeof(int)*(m+n));
    for (int i = 0; i < n; i++)
	{
		A[m + i] = B[i];
	}
    for(int i=0;i<m+n-1;i++)
    {
        for(int j=0;j<m+n-1-i;j++)
        {
            if(A[j]>A[j+1])
            {
                int temp=A[j];
                A[j]=A[j+1];
                A[j+1]=temp;
            }
        }
    }
}

发表于 2022-04-17 11:57:07 回复(0)

莫小雨so

void merge(int* A, int ALen, int m, int* B, int BLen, int n) {
    // write code here
    int i = 0, j = 0, k = 0;
    for(i = n - 1, k =  n + m - 1, j = m - 1;  i >= 0;)
    {
        *(A + (k--)) = (*(B + i) > *(A + j) || j < 0 )? *(B + (i --)) : *(A + (j--));
    }
}

发表于 2022-03-09 23:11:41 回复(0)

xiaolock883

先将B[]的全部链接到A[]的后半部分，再对整体进行冒泡排序。

void merge(int* A, int ALen, int m, int* B, int BLen, int n) {
    // write code here
    int i,j,tmp;
    i = ALen;
    j = 0;
    while(i<ALen+BLen)
    {
        A[i] = B[j];
        i++;
        j++;
    }
    for(i = 0;i<ALen+BLen;i++)
    {
        for(j = 0;j<ALen+BLen-i-1;j++)
        {
            if(A[j]>A[j+1])
            {
                tmp = A[j];
                A[j] = A[j+1];
                A[j+1] = tmp;
            }
        }
    }
}

发表于 2021-12-01 16:52:16 回复(1)

小酷爱

我这人比较太懒，所以就挑好写的来，大家别学我

#include <math.h>

int cmp(const void* e1, const void* e2)
{
    return *(int*)e1 - *(int*)e2;
}

void merge(int* A, int ALen, int m, int* B, int BLen, int n) {
    //把B数组合并到A数组后qsort升序排一下
    //这里其实没必要传ABLen过来，有mn就够了
    int i = 0, j = 0;
    for(i=m; i<ALen+BLen; i++)
    {
        A[i] = B[j++];
    }
    qsort(A, ALen+BLen, sizeof(int), cmp);
}

发表于 2021-11-08 03:41:58 回复(0)

勇敢牛牛，不怕困难！

void merge(int* A, int ALen, int m, int* B, int BLen, int n) {
  int i = m - 1, j = n - 1, k = m + n - 1;
  while (i >= 0 && j >= 0)
    *(A + k--) = *(A + i) > *(B + j) ? *(A + i--) : *(B + j--);
  while (j >= 0)
    *(A + k--) = *(B + j--);
}

发表于 2021-09-29 17:49:09 回复(0)

牛客213438852号

从后向前选大的写过去

时间复杂度O(m+n),空间复杂度O(1)

void merge(int* A, int ALen, int m, int* B, int BLen, int n) {
    // write code here
    if(B==NULL||BLen<=0||n<=0) return;
    for(int i=m-1,j=n-1,t=m+n-1;i>=0||j>=0;)
    {
        if(i<0) A[t--]=B[j--];
        if(j<0) A[t--]=A[i--];
        if(i>=0&&j>=0){
            if(A[i]>B[j]) A[t--]=A[i--];
            else A[t--]=B[j--];
        }
    }
}

发表于 2021-09-15 10:39:28 回复(0)

牛客830308422号

void merge(int* A, int ALen, int m, int* B, int BLen, int n) {
    // write code here
    int temp[1000] = {0};
    int i, j, idx;
    i = j = idx = 0;
    
    while (j < n) {
        if (i < m) {
            temp[idx++] =  A[i] < B[j] ? A[i++] : B[j++];
        } else {
            temp[idx++] = B[j++];
        }
    }
    while (i < m) {
        temp[idx++] = A[i++];
    }
    
    for (i = 0; i < m + n; i++) {
        A[i] = temp[i];
    }
}

发表于 2021-09-01 00:43:07 回复(0)

牛客896362385号

/**
 * 
 * @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,j;
    j=0;
    int p;
    for(i=m;i<(BLen+ALen);i++)
    {
        if(j != n)
        {
            A[i] = B[j] ;
                j++;
            }
        
        
    }   
    for(i=0;i<(BLen+ALen);i++)
    {
        for(j=i;j<(BLen+ALen);j++)
        {
            if(A[i]>A[j])
            {
                p =A[i];
                A[i] =A[j];
                A[j]= p;
            }
            
        }
    }
    for(i=0;i<6;i++)
    {
        printf("%d",A[i]);
        
    }
    
    // write code here
}

发表于 2021-08-10 11:22:31 回复(0)

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)