165

问答题 165 /393

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

参考答案

参考回答:

解法一:
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;
}
}
};