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
</br>
Solution
The objective of the problem is to find the median of the combination of two sorted arrays, therefore the most obvious way to solve this problem is to first combine these two sorted arrays and then decide which is the median of the new array.
However, this method may lack in efficiency for we will waste time on re-sorting the array. We need something better than this. The goal is to find median under O(log (m+n)) time so we cannot simply insert the element from array B into array A; instead, we should try to achieve this in one pass.
Hence, the solution can be established.
Firstly, consider how to determine a median of an array: median is the number at the middle position of a sorted array. Hence, we only have to find the middle element of the combination of two array. Instead of re-sorting two arrays, we can divide both sorted arrays into two parts, as nums1[0,i],nums1[i,m],nums2[0,j]and nums2[j,n] and then put nums1[0,i] and nums2[0,j] in one set, nums1[i,m] and nums2[j,n] into another.
Left_set | Right_set
A[0], A[1], ..., A[i-1] | A[i], A[i+1], ..., A[m-1]
B[0], B[1], ..., B[j-1] | B[j], B[j+1], ..., B[n-1]
As two arrays are sorted, we only have to achieve requirements below in order to find the right median.
[a]. The maximum of the left_set is smaller than the minimum of the right_set;
[b]. The size of the left_size and right_set should be the same.
If the above the requirements is achieved, then we simply have to compute the median by median = (max(left_part) + min(right_part))/2.
Then, the next issue we have to deal with is how to make sure the requirement is met. Then, to ensure these two conditions, we just need to ensure:
(1) i + j == m - i + n - j (or: m - i + n - j + 1)
(2) B[j-1] <= A[i] && A[i-1] <= B[j]
Therefore, we can have following steps.
[1] Set min = 0, max = m; then the search range is [min, max].
[2] Set i = (min + max)/2, j = (m + n + 1)/2 - i.
//By setting the value of i and j in this way,
//we can make sure the length of both set is equal.
[3] There are only 3 situations to deal with:
<a> B[j-1] <= A[i] and A[i-1] <= B[j]
Indicates the right `i`, return median;
<b> B[j-1] > A[i]
Indicates A[i] is too small.
We must adjust i to get B[j-1] <= A[i], hence we must increase i.
By adjusting the search range to [i+1, max], B[j-1] is decreased and A[i] is increased, and B[j-1] <= A[i] may be satisfied.
So, set min = i+1, and goto <2>.
<c> A[i-1] > B[j]
Indicates A[i-1] is too big. And we must decrease i to achieve A[i-1]<=B[j].
So we must adjust the search range to [min, i-1].
Set max = i-1, and goto <2>.
By adjusting the value of i and j, we can find where is the right place to divide two arrays.
When the right i is found, the median should be:
(when m + n is odd)
max(A[i-1], B[j-1]) ;
(when m + n is even)
(max(A[i-1], B[j-1]) + min(A[i], B[j]))/2 ;
The code is shown as below:
Java
public class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length, n = nums2.length;
int max_of_left = 0, min_of_right = 0;
if (m > n){
int[] temp = nums1;
nums1 = nums2;
nums2 = temp;
int temp_num = m;
m = n;
n = temp_num;
}
int min = 0, max = m, mid = (m + n + 1) / 2;
while (min <= max){
int i = (min + max) / 2;
int j = mid - i;
if (i < m && nums2[j-1] > nums1[i])
// i is too small
min = i + 1;
else if (i > 0 && nums1[i-1] > nums2[j])
// i is too big
max = i - 1;
else{
// i is perfect
if (i == 0)
max_of_left = nums2[j-1];
else if (j == 0)
max_of_left = nums1[i-1];
else
max_of_left = Math.max(nums1[i-1], nums2[j-1]);
if ((m + n) % 2 == 1)
return max_of_left;
if (i == m)
min_of_right = nums2[j];
else if (j == n)
min_of_right = nums1[i];
else
min_of_right = Math.min(nums1[i], nums2[j]);
return (max_of_left + min_of_right) / 2.0;
}
}
return 0;
}
}
</br>
