【每日一题】1. 牛客网——合并两个有序数组

1.题目描述

给出一个有序的整数数组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]

题目链接🔗

2. 思路分析

1. 题目已经明确表明，A数组足够大，那么我们就不需要开辟额外的空间，直接拿A 数组操作
2. 因为是合并数组，所以就需要双指针，那么我们开辟指针i，指针j，一个指向A的m-1，一个指向B的n-1，两个指针移动前我们还需要定义一个index = m + n - 1代表合并数组的最后一个元素位置
3. 开始移动，让A[i]，B[j]比较谁大，谁大就合并谁
4. 最后判断一下B合并完成没有，B没有合并完的话，直接把B丢进A

3. 代码

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

运行结果：

4.复杂度分析

• 时间复杂度：O(m + n)
• 空间复杂度：O(1)