合并两个有序的数组

（牛客网—牛客题霸算法篇—NC22）

题目描述

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

数据范围：0≤n,m≤100，Ai <=100，Bi<=100

注意：

1.保证 A 数组有足够的空间存放 B 数组的元素， A 和 B 中初始的元素数目分别为 m 和 n，A的数组空间大小为 m+n

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

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

思路

Java实现


先将数组A中的数据整体向后移动n个位置，将前n个位置空余出来。

之后分别比较两个数组当前位置上的数据大小，将较小的数值放入A数组前面的空余位置。之后数组索引分别向后移动，继续上述过程。

直到一个数组所有的数据排序完成，将另一个数组的数据依次放入A数据的后续位置。

代码实现

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