There are two sorted arrays A and B 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)).
Updated 09/22/2016: http://www.lifeincode.net/programming/leetcode-median-of-two-sorted-arrays-more-elegant-solution/
Analysis
We can solve this problem with the algorithm: Finding the Kth element in two sorted arrays. It’s quite straight forward. For example, supposing the total length of two arrays is N. If N is an odd number, we need to find the (N + 1) / 2 th number in two arrays, otherwise we need to find N / 2 th and (N + 1) / 2 th number and return the average of them.
The question requires a solution of O(log(m + n)) complexity. So we cannot do a linear search in these two arrays. But we can use a solution which is very similar to binary search.
For example, assuming we have the following two sorted arrays.
[table]
0, 1, 2, 3, 4, 5
a0, a1, a2, a3, a4, a5
[/table]
[table]
0, 1, 2, 3, 4, 5
b0, b1, b2, b3, b4, b5
[/table]
In this solution, we use mid = length / 2 to calculate the mid point position. The mid element of array A is A[3], and the mid element of array B is B[3]. We can divide each of them into two parts:
A_1(A[0], A[1], A[2]), A_2(A[3], A[4], A[5])
B_1(B[0], B[1], B[2]), B_2(B[3], B[4], B[5]).
Now we can compare A[3] with B[3]. If A[3] <= B[3], we know that the second part of B is equal or larger than any elements in the first part of A and B. We want the K th element in these two arrays. We have two situation here.
- If K is smaller than the length of A_1 and B_1, we know that this element should not be in B_2. So we can throw this part and continue searching K th element in A and B_1.
- If K is larger than the length of A_1 and B_1, K th element is not in A_1. Otherwise K will be smaller than the sum of length of A_1 and B_1. And then we can continue searching K – B_1.length th element in A_2 and B.
It’s quite similar for the situation A[3] > B[3]. The code is as follow.
Code
|
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 37 38 39 40 |
public class Solution { public double findMedianSortedArrays(int A[], int B[]) { int lengthA = A.length; int lengthB = B.length; if ((lengthA + lengthB) % 2 == 0) { double r1 = (double) findMedianSortedArrays(A, 0, lengthA, B, 0, lengthB, (lengthA + lengthB) / 2); double r2 = (double) findMedianSortedArrays(A, 0, lengthA, B, 0, lengthB, (lengthA + lengthB) / 2 + 1); return (r1 + r2) / 2; } else return findMedianSortedArrays(A, 0, lengthA, B, 0, lengthB, (lengthA + lengthB + 1) / 2); } public int findMedianSortedArrays(int A[], int startA, int endA, int B[], int startB, int endB, int k) { int n = endA - startA; int m = endB - startB; if (n <= 0) return B[startB + k - 1]; if (m <= 0) return A[startA + k - 1]; if (k == 1) return A[startA] < B[startB] ? A[startA] : B[startB]; int midA = (startA + endA) / 2; int midB = (startB + endB) / 2; if (A[midA] <= B[midB]) { if (n / 2 + m / 2 + 1 >= k) return findMedianSortedArrays(A, startA, endA, B, startB, midB, k); else return findMedianSortedArrays(A, midA + 1, endA, B, startB, endB, k - n / 2 - 1); } else { if (n / 2 + m / 2 + 1 >= k) return findMedianSortedArrays(A, startA, midA, B, startB, endB, k); else return findMedianSortedArrays(A, startA, endA, B, midB + 1, endB, k - m / 2 - 1); } } } |
If the length of an array is smaller or equal than zero, we know that we can directly get the K th element from the other array.
And If K = 1, we can just compare the first element and decide which one is the answer.
One thing needs to mention is that the comparison of k and the length of A_1 and B_1. We not only throws the half part of an array, we also throws the mid element out. So we will compare k with n / 2 + m / 2 + 1. And we throws half of the element like k – n / 2 – 1 or k – m / 2 – 1, in which “1” denoting the mid element. We are doing this because it can make sure that every time we will throw at least one element, otherwise sometimes it is possible that the solution is not able to stop.
Complexity
The complexity of this algorithm is O(log (m + n)).