Merge Sorted Array
Given two sorted integer arrays nums1 andnums2, 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 fromnums2. The number of elements initialized in nums1 and nums2 are m and nrespectively.
题目说，给你两个排序好的vactor数组，把数组2融合到数组1中，数组1的长度是足够的。融合后也是排序的。
void merge(vector<int>& nums1,int m, vector<int>& nums2, int n)
图示的话就是这样
我们观察一下，数组1是给了足够多的空间，所以我们要好好利用后面那段长为n的空间。
既然融合兼排序，那么最好的情况就是，每一次扫描都能摆好一个元素，这样扫描完毕，数组就融合且排序好了。
如果我们是从前往后扫描，可以想象，数组1中前m项的元素可能会牵一发动全身。所以我们把注意力集中到数组1的后n项空闲空间去。
我们可以从后往前扫描两个数组，对于数组1来说，就是从下标m-1开始往前扫描。
因为这两个数组是有序的，所以，这时候比较出来的较大值就是最大值了。假设这个数组。
456和123，3和6比较出来的较大值6就是最大值。我们用3个下标分别表示数组1元素的尾，数组2元素的尾，数组1的最终尾（就是n+m-1处）
我们把较大值从数组1的n+m-1下标开始从后往前保存。
这时，第一次扫描比较出来的较大值6就是两个数组的最大值，它放在下标m+n-1的位置，也就是最终的位置了。这个6是来自数组2的，那么index2前移。然后，同时index前移。
再比较3和5，较大值5，也就是剩余元素的当前最大值，放到index位置，也是最终位置。就这么一直扫描，直到数组1或者数组2（任一）被扫描完。
数组1先扫描完和数组2先扫描完是有点区别的。先分析数组2先扫描完毕。看这个情况（每次只扫描一个数，图片篇幅有限，连续的我就连续在一起了）
发生什么了呢，其实，数组2扫描完毕之后，数组1不管还剩多少元素，它们都是有序的。数组2先扫描完，也就是，数组2的最小值，比数组1剩下的元素还要大而已，所以数组2先扫描完毕的话，融合兼排序就完成了。
我们看先扫描完数组1的。
扫扫扫。到这一步，数组1即将扫描完毕了
下标前移，此时数组1扫描完毕
这时候的情况就是，数组1的最小值，比数组2剩余的元素还要大。这时候只要把数组2的元素按顺序存入数组1中就可以了（这个例子的情况就是按6、5、4的顺序）。
Leetcode的AcceptedSolutions Runtime Distribution（15-07-24）
源码：
#include <iostream>
#include <vector>
using namespace std;
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n);
void out(vector<int>);
int main()
{
vector<int> a;
a.push_back(-1);
a.push_back(0);
a.push_back(1);
a.push_back(1);
a.push_back(0);
a.push_back(0);
a.push_back(0);
a.push_back(0);
a.push_back(0);
vector<int> b;
b.push_back(-1);
b.push_back(0);
b.push_back(2);
b.push_back(2);
b.push_back(3);
merge(a, 4, b, 5);
out(a);
out(b);
return 0;
}
void out(vector<int> a)
{
int s = a.size();
for (int i = 0; i < s; i++)
{
cout << a[i] << " ";
}
cout << endl;
}
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n){
////////////////////////////////////////////////////////
//FromBackByIndex
////////////////////////////////////////////////////////
int index1 = m - 1;
int index2 = n - 1;
int index = m + n - 1;
if (0 == n) return;
if (0 == m)
{
while (index >= 0)
{
nums1[index] = nums2[index2];
index2--;
index--;
}
return;
}
while (index1 >= 0 && index2 >= 0)
{
if (nums1[index1] > nums2[index2])
{
nums1[index] = nums1[index1];
index1--;
index--;
}
else
{
nums1[index] = nums2[index2];
index2--;
index--;
}
}
if (-1 == index2) return;//index2等于-1退出（也就是index1等于-1才往下执行）
while (index >= 0)
{
nums1[index] = nums2[index2];
index2--;
index--;
}
//if (-1 == index1)//只有index1等于-1才执行
//{
// while (index >= 0)
// {
// nums1[index] = nums2[index2];
// index2--;
// index--;
// }
//}
}