Algorithm Puzzles: Median of Two Sorted Arrays

Algorithm Puzzles everyday every week sometimes: Median of Two Sorted Arrays

Puzzle

Puzzle from leetcode:

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0
Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

Solution

The first came out solution is using merge sort since the sub-vectors are already sorted. The funny part is the puzzle requests time complexity should be O(log (m+n)), which is same as merge sort.

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
class Solution {
public:
double findMedianSortedArrays(const vector<int>& nums1,const vector<int>& nums2) {
vector<int> nums3;
nums3.resize(nums1.size()+nums2.size());

auto iter1 = nums1.begin();
auto iter2 = nums2.begin();
auto iter3 = nums3.begin();

for(;; ++iter3){
if(iter1 == nums1.end()){
std::copy(iter2,nums2.end(),iter3);
break;
}
if(iter2 == nums2.end()){
std::copy(iter1,nums1.end(),iter3);
break;
}
if(*iter1<=*iter2){
*iter3 = *iter1;
++iter1;
}else{
*iter3 = *iter2;
++iter2;
}
}

if(nums3.size()%2 == 1){
return nums3[(nums3.size()-1)/2];
}else{
return (nums3[nums3.size()/2] + nums3[nums3.size()/2 - 1])/2.0;
}

}
};

Time complexity: O(log(m+n))

Result I got:

Better than 98.75%. BTW it seems I can get different result with the exactly same code…