Problem: Please implement a function which gets the intersection of two sorted arrays. Assuming numbers in each array are unique.
Solution 1: With O(m+n) Time
Therefore, if we search each number of an array with length n from an array with lengthm, its overall time complexity is O(nlogm). If m is much greater than n, O(nlogm) is actually less than O(m+n).
==One small improvement is to track the last return index when do binary search, and ignore the smaller part in next binary search.
Solution 1: With O(m+n) Time
void GetIntersection_solution1(const vector<int>& array1,
const vector<int>& array2,
vector<int>& intersection)
{
vector<int>::const_iterator iter1 = array1.begin();
vector<int>::const_iterator iter2 = array2.begin();
intersection.clear();
while(iter1 != array1.end() && iter2 != array2.end())
{
if(*iter1 == *iter2)
{
intersection.push_back(*iter1);
++ iter1;
++ iter2;
}
else if(*iter1 < *iter2)
++ iter1;
else
++ iter2;
}
}
Solution 2: With O(nlogm) TimeTherefore, if we search each number of an array with length n from an array with lengthm, its overall time complexity is O(nlogm). If m is much greater than n, O(nlogm) is actually less than O(m+n).
==One small improvement is to track the last return index when do binary search, and ignore the smaller part in next binary search.
void GetIntersection_solution2(const vector<int>& array1,
const vector<int>& array2,
vector<int>& intersection)
{
intersection.clear();
vector<int>::const_iterator iter1 = array1.begin();
while(iter1 != array1.end())
{
if(binary_search(array2.begin(), array2.end(), *iter1))
intersection.push_back(*iter1);
}
}
The second solution works nicely even if the shorter array (here length n) is unsorted.
Read full article from Coding Interview Questions: No. 24 - Intersection of Sorted Arrays