88. Merge Sorted Array

Title

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 nums1 and nums2 are m and n respectively.

Solutions

仅仅是把测试用例都过了…

class Solution { public: void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { if(m == 0) {//如果nums1为空，直接将nums2拷贝给nums1 nums1 = nums2; return; } int i = 0, j = 0; auto beg1 = nums1.begin(); auto beg2 = nums2.begin(); const int nums1Max = *(beg1+m-1); //因为要合并到nums1上，根据j与n的大小判断是否合并完成 while(j<n && *(beg2+j)<=nums1Max) {//如果nums2中的值小于nums1中最大值，则很简单 if(*(beg1+i) >= *(beg2+j)) {//如果nums2值小于nums1值，++i;否则，执行插入 nums1.insert(beg1+i, *(beg2+j)); ++j; beg1 = nums1.begin(); //每次更新vector,都会使其迭代器失效，故重定义。 } ++i; } i = m+j; while(j<n){//考虑nums2中值大于nums1的最大值，单独处理 nums1.insert(beg1+i, *(beg2+j)); beg1 = nums1.begin(); ++i; ++j; } //为过测试用例 nums1.erase(nums1.begin()+m+n, nums1.end()); } };

runtime: 8ms

Reference

vector

vctor::insert

－－－

别人的思路：

从后往前移动，将最大的数一步移动到指定点nums1[m+n-1]。这样时间复杂度为O(m+n)。

class Solution { public: void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { if (n == 0) return; int all = m+n-1; m--; n--; while(m >=0 && n >=0) nums1[all--] = (nums1[m]> nums2[n])? nums1[m--]:nums2[n--];//条件执行语句，m--只在被调用是执行 while(n >= 0)//当nums2中还有数时 nums1[all--] = nums2[n--]; } };