NC22 合并两个有序的数组

题目链接：https://www.nowcoder.com/practice/89865d4375634fc484f3a24b7fe65665

题目描述

给出一个有序的整数数组 A 和有序的整数数组 B ，请将数组 B 合并到数组 A 中，变成一个有序的升序数组

数据范围： 0≤n,m≤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]

解题代码

import java.util.*;
public class Solution {
    public void merge(int A[], int m, int B[], int n) {
        int p1 = 0, p2 = 0;
        //新开一个M+n大小的数组
        int[] sorted = new int[m + n];
        int cur;
        //循环选择
        while (p1 < m || p2 < n) {
            if (p1 == m) {
                cur = B[p2++];
            } else if (p2 == n) {
                cur = A[p1++];
            } else if (A[p1] < B[p2]) {
                cur = A[p1++];
            } else {
                cur = B[p2++];
            }
            sorted[p1 + p2 - 1] = cur;
        }
        //移动
        for (int i = 0; i != m + n; ++i) {
            A[i] = sorted[i];
        }
    }
}

本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名，转载请...
最后编辑时间为: 2022/07/23 23:17:36