Given two sorted integer 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 nums2.The number of elements initialized in nums1and nums2 are m and n respectively.
问题：
两个有序数组，合并成一个有序数组。如果第一个数组空间足够容纳两个数组。
Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.The number of elements initialized in nums1and nums2 are m and n respectively.
问题：
两个有序数组，合并成一个有序数组。如果第一个数组空间足够容纳两个数组。
分析：
考虑到num1数组非常大，能够直接在num1数组上进行合并，可是要讲究效率。
假设单纯从前往后合并，那么效率会很低，由于a数组后面的数字须要不停的移动。
换一种思路，我们採用从后往前合并。首先计算出总长度。设置一个指针从num1数组最后往前移动。
void merge(int* nums1, int m, int* nums2, int n) {
int newIndex=m+n-1;
int nums1I=m-1,nums2I=n-1;
while(nums1I>=0 && nums2I>=0){
if(nums1[nums1I]>=nums2[nums2I]){
nums1[newIndex]=nums1[nums1I];
newIndex--;
nums1I--;
}else{
nums1[newIndex]=nums2[nums2I];
newIndex--;
nums2I--;
}
}
while(nums1I>=0){
nums1[newIndex]=nums1[nums1I];
newIndex--;
nums1I--;
}
while(nums2I>=0){
nums1[newIndex]=nums2[nums2I];
newIndex--;
nums2I--;
}
}
总结：字符串合并时，我们更应该考虑从后往前这样的思路。
附C++代码
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
vector<int> result;
vector<int>::iterator iter1=nums1.begin();
vector<int>::iterator iter2=nums2.begin();
while(iter1!=nums1.begin()+m && iter2!=nums2.begin()+n){
if(*iter1<=*iter2){
result.push_back(*iter1);
++iter1;
}else{
result.push_back(*iter2);
++iter2;
}
}
while(iter1!=nums1.begin()+m){
result.push_back(*iter1);
++iter1;
}
while(iter2!=nums2.begin()+n){
result.push_back(*iter2);
++iter2;
}
nums1.swap(result);
}
};
本文转自mfrbuaa博客园博客，原文链接：http://www.cnblogs.com/mfrbuaa/p/5098676.html，如需转载请自行联系原作者
