问题描述

给出两个有序的整数数组 A 和 B，请将数组 B 合并到数组 A 中，变成一个有序的数组
注意：可以假设 A 数组有足够的空间存放 B 数组的元素，A 和 B 中初始的元素数目分别为 A 和 B。

输入描述:
输入两个数组、两个长度

输出描述:
排好序的数组

示例

示例1

输入
[1,2,3],3,[4,5,6],3

输出
[1,2,3,4,5,6]

解决思路

分析

本题采用从 A 数组右侧开始放置元素的方式排序，来避免多次循环的问题。

方法

1. 通过循环A/B数组，从A数组的右侧开始放置元素。

代码实现

public class Solution {
    public void merge(int A[], int m, int B[], int n) {
        int index = A.length - 1;
        int curA = m - 1;
        int curB = n - 1;

		// A/B元素同时包含
        while (curA >= 0 && curB >= 0) {
            if (A[curA] > B[curB]) {
                A[index--] = A[curA--];
            } else {
                A[index--] = B[curB--];
            }
        }
		// 只包含A数组元素
        while (curA >= 0) {
            A[index--] = A[curA--];
        }
		// 只包含B数组元素
        while (curB >= 0) {
            A[index--] = B[curB--];
        }
    }
}

小伙伴如果想测试的话，可以直接到牛客网这个链接做测试

合并两个有序的数组-牛客网