[Leetcode]Median of Two Sorted Array
The trickiest part of this problem is to find the median in a O(log(m + n)) runtime complexity. It is natural to think of merging the two sorted arrays first and find the midst element of the merged array. This approach results in an O(n) time and space complexity. It is not that bad, but not good enough to pass this test.
To reduce time complexity, we must come up with an approach to shrink size of the arrays and avoid traversing every element of them. Actually, this problem is quite similar to the problem "find the k-th element of two sorted arrays". In this case, we just need to find the (m + n)/2-th element with the exactly same approach.
Before writing code, we must know several facts about the "find the k-th element of two sorted arrays" problem:
When either array is empty, the program should return the k-th element of the other.
When k = 1, the program should return the smaller element between the first elements of the arrays.
If the k/2-th element of array A is smaller than the k/2-th element of array B, i.e. A[k/2 - 1] < B[k/2 - 1], the first k/2 elements can never be larger than the k-th element of A and B, and vice versa. In other word, if A[k/2 - 1] < B[k/2 -1], the first k/2 elements in A should be discarded, and vice versa.
If the k/2-th elements of A and B are equal, the program should return this element as the k-th element of the two arrays
With this approach, it is always assumed that A is smaller than B in size. Otherwise, k/2 might be out of B's index when A is much larger than B in size. So there must be a line to deal with the situation that A's size is larger than B's. The code is shown below:
Java:
public class Solution { public double findMedianSortedArrays(int[] A, int[] B){ int len = A.length + B.length; if(len % 2 == 1) return (double)findMedian(A, B, 0, 0, len / 2 + 1); else return (findMedian(A, B, 0, 0, len / 2) + findMedian(A, B, 0, 0, len / 2 + 1)) / 2.0; } public int findMedian(int[] A, int[] B, int as, int bs, int k){ int alen = A.length - as, blen = B.length - bs; if(alen > blen) return findMedian(B, A, bs, as, k); if(alen == 0) return B[bs + k - 1]; if(k == 1) return Math.min(A[as], B[bs]); int pa = Math.min(k / 2, alen), pb = k - pa; if(A[as + pa - 1] < B[bs + pb - 1]) return findMedian(A, B, as + pa, bs, k - pa); else if(A[as + pa - 1] > B[bs + pb - 1]) return findMedian(A, B, as, bs + pb, k - pb); else return A[as + pa - 1]; } }
Python:
class Solution: # @return a float def findMedianSortedArrays(self, A, B): total = len(A) + len(B) if total % 2 == 1: return self.findMedian(A, B, total / 2 + 1) / 1.0 else: return (self.findMedian(A, B, total / 2) + self.findMedian(A, B, total / 2 + 1)) / 2.0 def findMedian(self, a, b, k): if len(a) > len(b): return self.findMedian(b, a, k) if len(a) == 0: return b[k - 1] if k == 1: return min(a[0], b[0]) pa = min(k / 2, len(a)) pb = k - pa if a[pa - 1] < b[pb - 1]: return self.findMedian(a[pa:], b, k - pa) elif a[pa - 1] > b[pb - 1]: return self.findMedian(a, b[pb:], k - pb) else: return a[pa - 1]
The algorithm can be improved so that we don't need to concern about if A is smaller than B in size. The improvement is simple: we compare the k/(len(A) + len(B))-th element of A to the counterpart of B, so that it always take away a proper portion of A rather than a fix number of elements. The code is shown below:
Java:
public class Solution { public double findMedianSortedArrays(int[] A, int[] B){ int len = A.length + B.length; if(len % 2 == 1) return (float)findMedian(A, 0, A.length - 1, B, 0, B.length - 1, len / 2); else return (findMedian(A, 0, A.length - 1, B, 0, B.length - 1, len / 2) + findMedian(A, 0, A.length - 1, B, 0, B.length - 1, len / 2 - 1)) / 2.0; } public int findMedian(int[] A, int as, int ae, int[] B, int bs, int be, int k){ int alen = ae - as + 1, blen = be - bs + 1; if(alen == 0) return B[bs + k]; if(blen == 0) return A[as + k]; if(k == 0) return Math.min(A[as], B[bs]); int ak = alen * k / (alen + blen), bk = k - ak - 1; if(A[as + ak] < B[bs + bk]) return findMedian(A, as + ak + 1, ae, B, bs, be, k - ak - 1); else if(A[as + ak] > B[bs + bk]) return findMedian(A, as, ae, B, bs + bk + 1, be, k - bk - 1); else return A[as + ak]; } }
Python:
class Solution: # @return a float def findMedianSortedArrays(self, A, B): total = len(A) + len(B) if total % 2 == 1: return self.findMedian(A, B, total / 2) / 1.0 else: return (self.findMedian(A, B, total / 2) + self.findMedian(A, B, total / 2 - 1)) / 2.0 def findMedian(self, a, b, k): if len(a) == 0: return b[k] if len(b) == 0: return a[k] if k == 0: return min(a[0], b[0]) pa = len(a) * k / (len(a) + len(b)) pb = k - pa - 1 if a[pa] < b[pb]: return self.findMedian(a[pa + 1:], b, k - pa - 1) elif a[pa] > b[pb]: return self.findMedian(a, b[pb + 1:], k - pb - 1) else: return a[pa]
