Leetcode 面试题 10.01. 合并排序的数组【C++】

地址：https://leetcode-cn.com/problems/sorted-merge-lcci/

题目

给定两个排序后的数组 A 和 B，其中 A 的末端有足够的缓冲空间容纳 B。 编写一个方法，将 B 合并入 A 并排序。

初始化 A 和 B 的元素数量分别为 m 和 n。

示例:

输入:
A = [1,2,3,0,0,0], m = 3
B = [2,5,6],       n = 3

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

解题思路

挺蠢的解法，思路是遍历数组B，将数组B中的元素逐个插入到数组A中合适的位置。

将遍历A,B数组用的下表i,j定义在函数作用域内，是因为A,B均为排序后的数组，所以已经查找过的部分就没必要再查找一次了。

第一层循环从数组B中逐个取出元素，在循环体内插入到数组A中，考虑两种情况，第一种情况A，的已排序部分有比B[i]大的数，所以需要进入第二层循环找到第一个比B[i]大的数的位置，将这个数及其后面的已排序的数整体后移一位（第三层循环），然后将B[i]插入到这个位置；第二种情况，B[i]比A中已排序部分的所有数都大，这时候 j == m + i 并且 A[m+i] 一定是等于0的，此时只需将B[i]插入到A的已排序部分的尾部即可。

还有一个思路是直接将数组B整体插入到数组A已排序部分的后面，然后对整个数组A进行一次排序。但我没有采用这个思路，是因为题目已经表明A,B是已排序数组，所以“已排序”这个特性是应该要考虑到的。

代码

class Solution {
public:
    void merge(vector<int>& A, int m, vector<int>& B, int n) {
        //分别作为两个数组的下标
        int i = 0;
        int j = 0;
        //遍历数组B
        for (i; i < n; i++) {
            //遍历数组A
            for (j; j < m + i; j++) {
                //将B[i]插入到A中合适的位置
                if (B[i] < A[j]) {
                    for (int k = m + i; k > j; k--) {
                        A[k] = A[k - 1];
                    }
                    A[j] = B[i];
                    break;
                }
            }
            //B[i]比A中现有的所有数都大，将B[i]插入到A的末尾
            if (j == m + i && A[m + i] == 0) {
                A[m + i] = B[i];
            }
        }
    }
};