Merge two given sorted integer array A and B into a new sorted integer array.
Example
A=
[1,2,3,4]
B=
[2,4,5,6]
return
[1,2,2,3,4,4,5,6]
Challenge
How can you optimize your algorithm if one array is very large and the other is very small?
class Solution { public: /** * @param A and B: sorted integer array A and B. * @return: A new sorted integer array */ int getPos(vector<int> &A, int start, int end, int target) { if(target > A[end]) return end+1; while(start<end) { int mid = (start+end)/2; if(A[mid] < target) start = mid + 1; else end = mid; } return start; } vector<int> mergeSortedArray(vector<int> &A, vector<int> &B) { // write your code here int lenA = A.size(), lenB = B.size(); vector<int> *pLarge, *pSmall; if(lenA > lenB){ pLarge = &A; pSmall = &B; } else{ pLarge = &B; lenA = B.size(); pSmall = &A; lenB = A.size(); } int i = 0, j = 0; while(j<lenB){ i = getPos(*pLarge, i, lenA-1, (*pSmall)[j]); pLarge->insert(pLarge->begin()+i, (*pSmall)[j++]); if(i == lenA) break; lenA++; } while(j<lenB) pLarge->push_back((*pSmall)[j++]); return *pLarge; } };