[NC]22. 合并两个有序的数组

🚩传送门：牛客题目

题目

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

注意：

1. 可以假设数组有足够的空间存放数组的元素

   和中初始的元素数目分别为和，的数组空间大小为

2. 不要返回合并的数组，返回是空的，将数组的数据合并到里面就好了

3. 数组在_[0,m-1]_的范围也是有序的

示例1

输入： A: [4,5,6,0,0,0]，m=3 B: [1,2,3]，n=3 返回值：A: [1,2,3,4,5,6]

解题思路：拷贝 + 排序

我的代码

import java.util.Arrays;
public class Solution {
    public void merge(int A[], int m, int B[], int n) {
        //1.拷贝
        System.arraycopy(B, 0, A, m, n);
        //2.排序
        Arrays.sort(A);
    }
}

解题思路：二路归并

此二路归并，从右向左比，比较大的数值并过去。

图：起始状态

图：二路归并演示示意图

我的代码

public class Solution {
    public void merge(int A[], int m, int B[], int n) {
       int i=m-1;//A
       int j=n-1;//B
       int t=m+n-1;
       //1.二者均非空选择较大值填入A[t]
       while(i>=0&&j>=0){
           if(A[i]>B[j]){
               A[t--]=A[i--];
           }else{
               A[t--]=B[j--];
           }
       }
       //2.B数组空了,将A剩余填入即可
       while(i>=0){
           A[t--]=A[i--];
       }
       //3.A数组空了,将B剩余填入即可
       while(j>=0){
            A[t--]=B[j--];
       }
    }
}