题目

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

常规方法 （常规的归并排序）

1.思路

1. 开辟一个新的空间，用来存储最后的结果，命名为中间数组
2. 同时遍历两个数组，用一个中间值存储对比后的数值，比较完成后，存储到中间数组
3. 将中间数组拷贝到A数组，完成本题

可以参考归并排序的标准说法：

1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4. 重复步骤3直到某一指针超出序列尾,将另一序列剩下的所有元素直接复制到合并序列尾

这就是一个归并排序的做法

2.代码

class Solution {
public:
    void merge(int A[], int m, int B[], int n) {
        // A有足够空间存储B数组元素
        // 使用一个中间值比较元素值

        if (m == 0) {
            std::copy(B, B+n, A);
            return ;
        }javascript:void(0);
        if (n == 0) {
            return ;
        }

        auto &a_arr = A;
        auto &b_arr = B;
        int res_arr[m+n];
        int a_index{0}, b_index{0}, res_index{0};

        while (a_index != m || b_index != n) {
            int tmp{0};
            int a_num = a_arr[a_index],
                b_num = b_arr[b_index];

            if (a_num < b_num) {javascript:void(0);
                tmp = a_num;

                if(a_index == m && b_index != n) {
                    tmp = b_num;
                    ++b_index;
                }
                if (a_index != m) {
                    ++a_index;
                }
            } else {
                tmp = b_num;

                if (b_index == n && a_index != m) {
                    tmp = a_num;
                    ++a_index;
                }

                if (b_index != n) {
                    ++b_index;
                } 

            }

            res_arr[res_index++] = tmp;
        }

        std::copy(res_arr, res_arr+m+n, A);
    }
};

3. 小结

该方法很容易想到，和之前的连接两个有序链表思路是一个样子的。当然后续的方法也是一致的，只是把链表换成了数组，数据载体不一样了。

而相对应的，这种方法容易理解而且能满足题目要求，可以直接使用。接下来说明以下其他方法。

不申请新空间的“归并排序”

从后往前处理，会发现不需要申请新的空间。

再简化一下思路，代码写出来会十分简单。

1. 思路

1. 直接使用数组A作为结果空间（题目说明了A足够大)；
2. 遍历两者，存入大的数字
3. 最终结果

2. 代码

class Solution {
public:
    void merge(int A[], int m, int B[], int n) {
        // A有足够空间存储B数组元素

        // 索引
        int a_index{m-1},
            b_index{n-1};

        int res_index{m+n-1};

        while (a_index >= 0 && b_index >= 0) {
            if (A[a_index] > B[b_index]) {
                A[res_index] = A[a_index];
                --a_index;
            } else {
                A[res_index] = B[b_index];
                --b_index;
            }
            --res_index;
        }

        while (b_index >= 0) {
            A[res_index] = B[b_index];

            --res_index;
            --b_index;
        }


    }
};

3. 小结

对比一下两者思路是一致的，代码实现有所区别，对比运行的时间是无差别的，内存占用却更多一些（疑惑点）。

第二个while不好理解。当其中一个数组完成遍历之后，剩余的数据就是有序了。比如下列数据：

先完成B遍历

A: 1 2 3 4 5
B: 2 3 4

# 一循环之后 B已经遍历完成
A: 1 2 2 3 3 4 4 5
B: 2 3 4

B未完成遍历

A: 2 2 3 4 5
B: 1 2

# 一循环之后
A: 2 2 2 2 3 4 5
B: 1 2

# 进入二循环
A: 1 2 2 2 3 4 5
B: 1 2

类似例子可以自己尝试手动推导一下。

而本题最重要的是归并的使用，常规方法才是解决实际问题的关键，而思路一致也有代码不同的可能。

其他方法

也可以参考链表的合并，对于链表使用next作为下一步，此处可以尝试使用全局变量设定index代替。此处不表。

2020-10-25