LeetCode: Merge Sorted Array

First try:

Iterate vector nums2 and insert each value into nums1 with bisection search. Time complexity is O(n*log(m))

Here are some explanations for the bisection part:

For line 14 and 15, they ensured that all elements on the left side of left is smaller than destination, while all elements on the right side of right is larger than destination.
即： left左边的都比nums2[i]小，right右边的都比nums2[i]大

when the number is not found, after finishing search, left will be 1 bigger than right, and left and right are adjacent.

To conclude, the searching result will be either a position which is just the position where element equals to destination or a one width range (right, left) that the destination should be located between it. (p.s. left=right+1 here)
             
So (left-1) or right will be the closet position a little smaller than destination. We need to insert the destination to the left of where value is a little larger than destination. So (eft-1)+1=left is the position to insert. (see line 21)

Line 22 and 23: after each for loop, reset the right to the most right element.  Since the number of elements has been changed by insert operation, so ++m. And pop a zero element after insertion in the vector nums2 to make it pass the leetcode test, or there will be unwanted zeros.

My algorithm has the advantage that we don't need to manage the size of vector nums1.

However, this is not the problem designed for. So I have to try again with the standard solution.  Orz

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

class Solution { public: void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { if(m==0) { nums1=nums2; return; } int left=0; int right=m-1; int middle=(left+right)/2; for(int i=0;i<n;i++){ while(left<=right){ middle=(left+right)/2; if(nums2[i]<nums1[middle]) right=middle-1; if(nums2[i]>nums1[middle]) left=middle+1; if(nums2[i]==nums1[middle]) { left=middle; break; } } nums1.insert(nums1.begin()+left,nums2[i]); nums1.pop_back(); right=++m-1; //Print vector to testTest /*for(int i=0;i<nums1.size();i++){ cout<<nums1[i]<<" " ; } cout<<endl;*/ } } };

Second try:
Comparing two vector from the last element with merge sort.
for process the comparisons between nums1 and nums2.
After that, if nums2 still has elements, keep adding them to nums1.
Time complexity: O(m+n)

Initial ugly codes:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

class Solution { public: void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { //these two special cases are concluded in normal case if(m==0) { nums1=nums2; return; } if(n==0) return; int index1=m-1; int index2=n-1; int index3=m+n-1; while(index1>=0 && index2>=0){ if( nums1[index1] >= nums2[index2] ){ nums1[index3]=nums1[index1]; index3--; index1--; } else{ nums1[index3]=nums2[index2]; index3--; index2--; } } //can be changed to simple while loop if(index1<0){ for(; index2>=0; index2--){ nums1[index3]=nums2[index2]; index3--; } } //codes below are not necessary if(index2<0){ for(; index1>=0;index1--){ nums1[index3]=nums1[index1]; index3--; } } } };

Modified version:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

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