LeetCode (Algorithms#4) ‒ Median of Two Sorted Arrays
Problem
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)).
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 idea behind this problem is quite simple. To find the median in O(log(n+m)), we need to perform some kind of binary search concurrently on both arrays. The difficulty is in making sure to consider all possible cases. Overall, there is a general case that performs the binary search, and a base case to chose the median among four or less remaining elements. The code below has the different cases commented. The idea is to keep track of how many elements have been removed from each side, and repeatedly split either array in half such that we remove the smaller or larger elements from the left or right side, respectively.
This is certainly not the most clean or efficient solution to this problem as there are many cases that need to be explicitly handled. Another solution is to use a recursive divide and conquer approach where you determine the two array's medians, and then recurse on the halves of the arrays that bring the medians closer (or equal to each other).
No comments:
Post a Comment