Merge Sorted Array

Given two sorted interger arrays nums1 and nums2,merge nums2 into nums1 as one sorted array.

Note:

You may assume that nums1 has enough space(size that is greater or equal to m+n)to hold additional elements from nums.The number of elements initialized in nums1 and nums2 are m and n respectively.

按照归并排序的惯性思路，因为归并排序给定的是一个数组的两个区间，所以通常情况下会借助O(n)大小的辅助空间。思路如下：

 1 class Solution
 2 {
 3 public:
 4     void merge(vector<int> &nums1, int m, vector<int> &nums2, int n)
 5     {
 6          vector<int> A;
 7          A.resize(m+n);
 8          int pa = 0, pb = 0, i = 0;
 9          while(pa < m && pb < n)
10          {
11                if(nums[pa] < nums1[pb])
12                    A[i ++] = nums1[pa ++];
13                else
14                    A[i ++] = nums2[pb ++];
15          }  
16          while(pa < m)
17                  A[i ++] = nums1[pa ++];
18          while(pb < n)
19                  A[i ++] = nums2[pb ++];
20          nums1.resize(m+n);
21          while(--i >= 0)
22                  nums1[i] = A[i];
23     }  
24 }

　　但是上述题目给定的条件更加灵活，因此可以采用尾插法，这样就不再需要辅助空间的开销，理解上也更加简洁：

 1 class Solution
 2 {
 3 public:
 4     void merge(vector<int> &nums1, int m, vector<int> &nums2, int n)
 5     {
 6         int pa = m-1, pb = n-1, i = m+n-1;
 7         while(pa >= 0 && pb >= 0)
 8         {
 9             if(nums1[pa] > nums2[pb])
10                 nums1[i --] = nums1[pa --];
11             else
12                 nums1[i --] = nums2[pb --];
13         }
14         while(pb >= 0)
15                 nums1[i --] = nums[pb --];
16     }   
17 }