题面

给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。

样例

1. 输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

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

2. 输入:
nums1 = [0], m = 0
nums2 = [6], n = 1

输出: [6]

算法

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

与合并有序链表类似。

1. 如果m为0，直接返回就可以了。如果n为0,则需要把nums2中前n个元素都搬到nums1中，返回。

2. 如果，m、n都不为0，计算合并后的元素数len = m+n, 我们从后往前为nums1[len--]赋max(nums1[m]nums2[n]), 之后较大的数组下标自减（已经比较后填入了nums1中），直到某个数组被遍历完。

3. 如果2之后，m == 0,那么代表nums1中的元素都已经填完了，就把nums2中剩下的元素按次序填入nums1中即可；如果 n == 0，即nums2填完了，那就结束，剩下的nums1本来就是有序的。

源码

 1 class Solution {
 2 public:
 3     void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
 4         if(n == 0)
 5             return ;
 6         else if(m == 0)
 7         {
 8             for(int i=0; i<n; i++)
 9                 nums1[i] = nums2[i];
10         }
11         
12         //从往前放置
13         int len = m+n-1;
14         m--; n--;
15         while(m >= 0 && n >= 0 && len >= 0)
16         {
17             if(nums1[m] < nums2[n])
18             {
19                 nums1[len] = nums2[n];
20                 len--; n--;
21             }
22             else
23             {
24                 nums1[len] = nums1[m];
25                 len--; m--;
26             }
27         }
28         if(m < 0)
29         {
30             for(int i=0; i<=n; i++)
31                 nums1[i] = nums2[i];
32         }
33     }
34 };