手写代码:合并两个有序数组
参考回答:
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; } } };