Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
Note:
- The number of elements initialized in nums1 and nums2 are m and n respectively.
- You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.
Example:
Input: nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n = 3 Output: [1,2,2,3,5,6]
把两个已排序数组合并成一个有序数组。注意是保存到nums1中。我一开始理解的是在合并过程中不能借助额外空间，所以用两个指针i,j指向两个数组，然后每次从nums2中找第一个小于nums1[i]的数，然后交换nums1[i]和nums2[j]，再调整nums2使有序。如此下去，nums1就是合并有序数组中的较小数组部分。
这个版本的完整代码如下：
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n)
{
if (n == 0)
return;
int i = 0;
while (i < m) {
int j = 0;
while (nums1[i] <= nums2[j] && i < m)
i++;
if (i >= m)
break;
swap(nums1[i], nums2[j]);
while (j < n – 1 && nums2[j] > nums2[j + 1]) {
swap(nums2[j], nums2[j + 1]);
j++;
}
i++;
}
for (int j = 0; j < n; j++) {
nums1[i++] = nums2[j];
}
}
};本代码提交AC，用时6MS。但是只击败了15%的人，仔细看看算法实现，最坏复杂度是$O(n*m)$，因为如果nums1={6,7,8,9,10}，nums2={1,2,3,4,5}，则nums1[i]每和nums2[0]交换一次，nums2调整时都要交换n-1次，所以最坏复杂度是$O(n*m)$。所以应该还有更好的算法。
看题解，发现我没有很好利用nums1的数组大小至少是n+m这个信息，这说明合并之后的整个数组，最大下标只能是n+m-1，所以我们可以对nums1和nums2从后往前比较，把更大的元素依次在nums1[n+m-1]往前放，这样共3个指针，他们之间不会有overlap。此算法的复杂度只有$O(max(n,m))$。
完整代码如下：
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n)
{
if (n == 0)
return;
int i = m – 1, j = n – 1, k = m + n – 1;
while (i >= 0 || j >= 0) {
int a = i >= 0 ? nums1[i] : INT_MIN;
int b = j >= 0 ? nums2[j] : INT_MIN;
if (a > b) {
nums1[k–] = a;
i–;
}
else {
nums1[k–] = b;
j–;
}
}
}
};本代码提交AC，用时3MS，果然快多了。
