排序与搜索——合并两个有序数组

题目
合并两个有序数组

---

题目很简单，一般人第一反应就是用插入排序的算法，但是实际上这种方法效率很低，所以普遍的采用以下这两种方法：
先介绍第一种，也就是官方最优解，下面是代码。

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
         int i = m - 1, j = n - 1, index = m + n - 1;
                   while (i >= 0 && j >= 0)
                   {
                             nums1[index--] = nums1[i] > nums2[j] ? nums1[i--] : nums2[j--];
                   }
                   while (j >= 0)
                             nums1[index--] = nums2[j--];

    }
};

单纯的程序很好理解，比较巧妙的一点是这个算法利用了nums1数组后面有n个0这个条件，所以nums1数组完全可以容纳全部数据。于是倒着插入数据，不断地向nums1数组尾中插入当前最大的数字。
有人可能会问数据会不会互相干扰，例如误把插入的数据当成nums1初始的数据。其实并不会的，因为当发生这种情况时，有index < i，我们看程序第一个循环（只有在这个循环中会发生数据污染，因为第二个循环不涉及nums1的初始数据），index值每次都会递减，i值只有一定条件下才递减，且最多递减min{m,n}次（i或者j递减到0就跳出循环），最少递减0次。我们按照极端情况计算，假设每次都递减i，在第一个循环的某次执行时已经递减了k次，那么现在index的值是m+n-1-k，i的值是m-1。我们换个形式，index值是 (m-1) + n - k，而i的值是(m-1)，很显然index的值永远大于i，也就不会发生index < i的情况了。
然后我们来看第二种方法，这种方法是我自己用的，先来看代码

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        vector<int> a(m + n);
        int j = 0, k = 0;
        for (int i = 0; i < m + n; i++)
        {
            // 注意！虽然逻辑1 3的执行内容相同，逻辑2 4的执行内容相同，
            // 但是因为要保证逻辑1 2先于逻辑3 4执行，所以必须像这样分开写
            if (j >= m) {   // 逻辑1
                a[i] = nums2[k++];
            } else if (k >= n) {    // 逻辑2
                a[i] = nums1[j++];
            } else if (nums2[k] <= nums1[j]) {  // 逻辑3
                a[i] = nums2[k++];
            } else if (k >= n || nums1[j] < nums2[k]) { // 逻辑4
                a[i] = nums1[j++];
            }
        }
        for (int i = 0; i < m + n; i++)
        {
            nums1[i] = a[i];
        }
    }
};

思路非常简单，和合并两个有序链表的思路一样，用两个指针遍历两个数据结构，每次比较两个指针指向数据的值，把较小的数字插入指定结构中，然后该指针向后移动。
说的更简单一点就是，创建一个新数组用来保存数据，然后遍历两个所给定的数组，将遍历得到的数字按顺序插入到这个新数组中，最后把新数组中的内容插入到nums1中。由于每次是把数字插入到新数组中，所以不用像插入排序那样每次插入要移动很多数据，所以效率也很高。

用时和第一种基本相同，并且逻辑较为简单