合并两个有序的数组

题目来源

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

题目描述

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

数据范围：|A_i| <=100∣A ， |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]

思路分析

• A数组的容量能够放下两个数组所有的元素，所以可以不用定义新的数组
• 从后往前遍历向A数组中对应位置，放入A、B数组比较得到的较大值，从后往前遍历可以避免A数组前面的数据被覆盖
• 如果最后B数组有剩余元素没有放入A数组，则按顺序将剩下的元素放入A，若A有剩余保持不变即可
  
  

代码展示

class Solution {
    
public:
    void merge(int A[], int m, int B[], int n) {
    
        int i = m + n - 1;
        m--;
        n--;

        while (n >= 0 && m >= 0)
        {
    
            //将大的数放入A数组最后的位置
            if (A[m] >= B[n])
            {
    
                A[i] = A[m];
                m--;
            }
            else
            {
    
                A[i] = B[n];
                n--;
            }
            i--;
        }

        //循环结束后如果B数组由剩余，则将剩下的按顺序放入A数组中
        while (n >= 0)
        {
    
            A[i] = B[n];
            i--;
            n--;
        }
    }
};

总结

这道题是面试中的常考题，核心思想就是从后向前遍历数组，避免数据被覆盖。如果从前往后遍历就需要定义一个数组，会造成空间的浪费。