手写代码：合并两个有序数组

Answer 1

参考回答：

解法一：

class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {

int num[m+n];//新建一个数组，对nums1和nums2排序，排完序赋值给nums1

int i = 0,j = 0,k = 0;
while(i<m && j<n){
if(nums1[i] <= nums2[j])
num[k++] = nums1[i++];
else
num[k++] = nums2[j++];
}
while(i < m) num[k++] = nums1[i++];
while(j < n) num[k++] = nums2[j++];
copy(num,num+m+n,nums1.begin());
}
};

解法二：

class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
vector<int> num(m+n);//与解法一类似，不过是新建一个vector
int i = 0,j = 0,k = 0;
while(i<m && j<n){
if(nums1[i] <= nums2[j])
num[k++] = nums1[i++];
else
num[k++] = nums2[j++];
}
while(i < m) num[k++] = nums1[i++];
while(j < n) num[k++] = nums2[j++];
nums1.assign(num.begin(),num.end());//nums1.swap(num)也可以
}
};

 

解法三：直接在nums1里进行操作，从nums1的尾部开始，取nums1和nums2中的最大值放入其中。如果n先到达0就能直接得到合并好的数组；如果m先到达0，只需将n剩下的元素复制到nums1中即可。

class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int k=m+n;
while(m>0 && n>0){
if(nums1[m-1] >= nums2[n-1]){
nums1[k-1] = nums1[m-1];
--k;
--m;
}
else{
nums1[k-1] = nums2[n-1];
--k;
--n;
}
}
while(n > 0){
nums1[k-1] = nums2[n-1];
--k;
--n;
}
}
};