首页 > 试题广场 >

合并两个有序数组

[编程题]合并两个有序数组
  • 热度指数：1472 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
现给出两个有序整型数组，其中array1按升序（从小到大）排序，array2按降序排序，请你将 array1和array2 合并到一个新的数组中，并保持新中的元素按升序排序。

说明:
给出 array1 和 array2 及其元素数量n 和 m ，返回合并后的新数组。

示例1

输入

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

输出

[1,2,4,5,6]
算法知识视频讲解
添加回答
卡农变骤头像 卡农变骤
         // write code here
        // 使用一个双指针的方式 第一个数组是升序，指针从0开始，第二个数组是降序，指针从m-1开始
        // 逐一判断两个数组的指针元素，哪个小就放哪个到自己定义的sort数组中。
        // 当其中一个数组遍历完毕了，再判断剩下的数组是哪个，如果是第一个数组的话就将剩下的元素顺序加入sort数组中
        // 如果剩下的是第二个数组的话(题目说了是降序)，那么就降序加入sort数组中
        int[] sort = new int[n+m];
        int i = 0; // 第一个数组的指针
        int p = m-1; // 第二个数组的指针
        int si = 0;
        while(i<n && p>=0){
            if(array1[i]<array2[p]){
                // 第一个数组的元素小于第二个数组元素
                sort[si++]=array1[i++];
            }else if(array1[i]>array2[p]){
                sort[si++]=array2[p--];
            }else{ // 两个数相等
                sort[si++] = array1[i++];
            }
        }
         
        if(p<=0){
                // 第二个数组已经放完了
                // 将第一个数组剩下的值全部放入即可
                for(int b = i;b<n;b++){
                    sort[si++] = array1[b];
                }
         }
        if(i>=n){
            for(int b = p;b>=0;b--){
                    sort[si++] = array2[b];
           }
        }
         
        return sort;
发表于 2022-06-16 23:04:40 回复(0)
牛客73799987号头像 牛客73799987号 
import java.util.*;

public class Solution {
    public int[] arrayMerge (int[] array1, int n, int[] array2, int m) {
        // write code here
        int [] ans = new int[n + m];
        int ixd = 0, i = 0, j = m - 1;
        while(j >= 0 && i < n && ixd < n + m){
            int num = 0;
            if(array1[i] > array2[j]) {
                num = array2[j--];
            }else{
                num = array1[i++];
            }
            ans[ixd++] = num;
        }
        while(i < n) ans[ixd++] = array1[i++];
        while(j >= 0) ans[ixd++] = array2[j--];
        return ans;
    }
}

这题的超时都不知道怎么判断的，再快也必须是O(n+m)呀

发表于 2022-02-23 15:08:25 回复(0)
早春的树i头像 早春的树i
用的杨辉三角，可以百分百通过 
public int combination (int r, int n) {
    if( r>n || r<0 || n<0) return 0;
    if(  r==n || r == 0 || n == 0) return 1;
    if( r == 1) return n;
    int[][] dp = new int[n+1][n+1];
    for(int i=0; i<n+1; i++) dp[i][0] = 1;
    for(int i=1; i<n+1; i++) {
        for(int j=1; j<=i; j++) {
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
        }
    }
    return dp[n][r];
}
发表于 2024-09-26 11:20:33 回复(0)
被GC的垃圾头像 被GC的垃圾
懒得写双指针了，直接懒人做法 
public int[] arrayMerge (int[] array1, int n, int[] array2, int m) {
        // write code here
        int[] res=new int[n+m];
        for (int i = 0; i < n; i++) {
            res[i]=array1[i];
        }
        for (int i = n; i < n + m; i++) {
            res[i]=array2[i-n];
        }
        Arrays.sort(res);
        return res;
    }

发表于 2022-08-31 10:08:24 回复(0)
2018年骑士总冠军头像 2018年骑士总冠军
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param array1 int整型一维数组 
     * @param n int整型 
     * @param array2 int整型一维数组 
     * @param m int整型 
     * @return int整型一维数组
     */
    public int[] arrayMerge (int[] array1, int n, int[] array2, int m) {
        // write code here
        int i = 0;
        int j = m-1;
        ArrayList<Integer> list = new ArrayList<>();
        while(i != n && j >= 0){
            if(array1[i] < array2[j]){
                list.add(array1[i]);
                i++;
            }else{
                list.add(array2[j]);
                j--;
            }
        }
        if(i == n){
            while(j >= 0){
                list.add((array2[j]));
                j--;
            }
        }
        if(j < 0){
            while(i != n){
                list.add(array1[i]);
                i++;
            }
        }
        int[] rtn = new int[list.size()];
        int index = 0;
        for(int k : list){
            rtn[index++] = k;
        }
        return rtn;
    }
}
发表于 2022-06-10 10:55:40 回复(0)
TPH-BETTER.头像 TPH-BETTER. 
import java.util.*;
 
 
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param array1 int整型一维数组 
     * @param n int整型 
     * @param array2 int整型一维数组 
     * @param m int整型 
     * @return int整型一维数组
     */
      public int[] arrayMerge (int[] array1, int n, int[] array2, int m) {
        int []arrayFinal=new int[m+n];
        int i=0;
        int j=m-1;
        for(int a=0;a<m+n;a++){
            if(i<n && j>=0){
                if(array1[i]>array2[j]){
                    arrayFinal[a]=array2[j];
                    j--;
                }else{
                    arrayFinal[a]=array1[i];
                    i++;
                }
            }else if(i>=n){
                arrayFinal[a]=array2[j];
                j--;
            }else{
               arrayFinal[a]=array1[i];
               i++; 
            }
        }
        return arrayFinal;
    }
}

发表于 2022-05-13 15:49:30 回复(0)
牛客962367364号头像 牛客962367364号
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param array1 int整型一维数组 
     * @param n int整型 
     * @param array2 int整型一维数组 
     * @param m int整型 
     * @return int整型一维数组
     */
    public int[] arrayMerge (int[] array1, int n, int[] array2, int m) {
        // write code here
         int[] result = new int[n+m];
        int index = m - 1;
        int bigArrayIndex = 0;
        for(int i =0; i<n; i++){
            int a1 = array1[i];
            while(index >= 0 && array2[index] <= a1){
                result[bigArrayIndex] = array2[index];
                index--;
                bigArrayIndex++;
            }
            result[bigArrayIndex] = a1;
            bigArrayIndex++;
        }
        if (bigArrayIndex < m+n){
            while(bigArrayIndex < m+n){
                result[bigArrayIndex] = array2[index];
                bigArrayIndex++;
                index--;
            }

        }
        return result;
    }
}
发表于 2022-04-22 14:56:30 回复(0)
行走的造粪机头像 行走的造粪机 
不讲码德法
import java.util.*;


public class Solution {
    public int[] arrayMerge (int[] array1, int n, int[] array2, int m) {
        // write code here
        int[]res=new int[m+n];
        int i=0,j=0,k=0;
        while(i<n){
            res[k++]=array1[i]; 
            i++;
        }
        while(j<m){
            res[k++]=array2[j];
            j++;
        }
        Arrays.sort(res);
        return res;
    }
}

发表于 2022-03-19 20:46:03 回复(0)
wanbf头像 wanbf 
说好的5秒呢，运行4秒你给我说超时
提交时间：2022-01-17 语言：Java 运行时间： 4001 ms 占用内存：9580K 状态：运行超时

import java.util.*;
 
 
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param array1 int整型一维数组
     * @param n int整型
     * @param array2 int整型一维数组
     * @param m int整型
     * @return int整型一维数组
     */
    public int[] arrayMerge (int[] array1, int n, int[] array2, int m) {
        // write code here
        int[] res = new int[m+n];
        int i=0;
        int j=m-1;
        int index=0;
        while(i<n && j>=0){
            if(array1[i]<array2[j]){
                res[index]=array1[i];
                i++;
            }else{
                res[index]=array2[j];
                j--;
            }
            index++;
        }
        while(i<n){
            res[index]=array1[i];
            i++;
            index++;
        }
        while(j>=0){
            res[index]=array2[j];
            j--;
            index++;
        }
        return res;
    }
}

发表于 2022-01-18 00:09:41 回复(2)
Caito0_0头像 Caito0_0
vector<int> arrayMerge(int* array1, int array1Len, int n, int* array2, int array2Len, int m) {
        // write code here
        vector<int> ans;
        int i=0, j=0;
        for(i;i<array1Len;i++)
            ans.push_back(array1[i]);
        for(j;j<array2Len;j++)
            ans.push_back(array2[j]);
        sort(ans.begin(),ans.end());
        return ans;
    }
发表于 2021-04-26 00:28:15 回复(0)
Kwai_Tourry头像 Kwai_Tourry
java 双指针merge 运行超时 
public int[] arrayMerge (int[] array1, int n, int[] array2, int m) {
        // write code here
        int[] res=new int[n+m];
        int i=0,j=m-1,k=0;    //双指针
        while(i<n&&j>=0){
            if(array1[i]<array2[j]) res[k++]=array1[i++];
            else if(array1[i]>array2[j]) res[k++]=array2[j--];
            else { res[k++]=array1[i++];res[k++]=array2[j--]; }
        }
        while (i<n) res[k++]=array1[i++];
        while (j>=0) res[k++]=array2[j--];
        return res;
    }

发表于 2021-02-04 12:51:07 回复(3)
牛客37697243号头像 牛客37697243号 
def sort(a, b, m, n):
    res = []
    index = 0
    for i in range(m + n - 1):
        a_curr = a[index]
        b_curr = b[n - 1]
        if a_curr < b_curr:
            res.append(a_curr)
            if index != m - 1:
                            index += 1
        else:
            res.append(b_curr)
            n = n-1
    return res

编辑于 2020-12-28 18:07:28 回复(0)
提交观点

问题信息

途虎 2021 Java工程师
来自：途虎养车2021秋招J...
上传者：小小
难度：
12条回答 4235浏览

热门推荐

通过挑战的用户

相关试题

合并两个有序数组

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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