Understand the problem:
The problem gives two sorted array, A and B. Find out the median of the two sorted arrays.
Note that the time complexity is required to be O(log(m+n)).
An initial thought was firstly merge the two arrays, then median is the number on A.length + B.length - 1 / 2. However, merging will take O(m + n) time, which however the algorithm asks for a solution in log time. So it is naturally to think about the binary search.
One thing must take note is the definition of the median of a sorted array. Note that the return number is double in the problem. So if the array length is even, e.g. 1, 2, 3, 4. The median is the average of 2 and 3, i.e., 2 + 3 / 2 = 2.5
Solution:
http://fisherlei.blogspot.com/2012/12/leetcode-median-of-two-sorted-arrays.html
http://www.lifeincode.net/programming/leetcode-median-of-two-sorted-arrays-java/
The problem is equivalent to find the kth element in the two sorted array. The key is to decide how to eliminate part of the array each recursion.
Code (Java):
public class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
if (nums1 == null || nums2 == null) {
return 0.f;
}
int n1 = nums1.length;
int n2 = nums2.length;
if ((n1 + n2) % 2 == 1) {
return findMedianHelper(nums1, nums2, (n1 + n2) / 2 + 1);
} else {
return (findMedianHelper(nums1, nums2, (n1 + n2) / 2) +
findMedianHelper(nums1, nums2, (n1 + n2) / 2 + 1)) / 2;
}
}
private double findMedianHelper(int[] nums1, int[] nums2, int k) {
if (nums1 == null || nums1.length == 0) {
return nums2[k - 1];
}
if (nums2 == null || nums2.length == 0) {
return nums1[k - 1];
}
if (k == 1) {
return Math.min(nums1[0], nums2[0]);
}
int n1 = nums1.length;
int n2 = nums2.length;
if (nums1[n1 / 2] > nums2[n2 / 2]) {
if ((n1 / 2 + n2 / 2 + 1) >= k) {
return findMedianHelper(Arrays.copyOfRange(nums1, 0, n1 / 2), nums2, k);
} else {
return findMedianHelper(nums1, Arrays.copyOfRange(nums2, n2 / 2 + 1, n2),
k - (n2 / 2 + 1));
}
} else {
if ((n1 / 2 + n2 / 2 + 1) >= k) {
return findMedianHelper(nums1, Arrays.copyOfRange(nums2, 0, n2 / 2), k);
} else {
return findMedianHelper(Arrays.copyOfRange(nums1, n1 / 2 + 1, n1),
nums2, k - (n1 / 2 + 1));
}
}
}
}
Edit on 4/27/20:
public class Solution { /* * @param A: An integer array * @param B: An integer array * @return: a double whose format is *.5 or *.0 */ public double findMedianSortedArrays(int[] A, int[] B) { // write your code here int n = A.length + B.length; if (n % 2 == 1) { return findMedianSortedArraysHelper(A, 0, B, 0, n / 2 + 1); } else { return ((double) findMedianSortedArraysHelper(A, 0, B, 0, n / 2) + findMedianSortedArraysHelper(A, 0, B, 0, n / 2 + 1)) / 2; } } private int findMedianSortedArraysHelper(int[] A, int startOfA, int[] B, int startOfB, int k) { if (startOfA >= A.length) { return B[startOfB + k - 1]; } if (startOfB >= B.length) { return A[startOfA + k - 1]; } if (k == 1) { return Math.min(A[startOfA], B[startOfB]); } int halfOfA = startOfA + k / 2 - 1 >= A.length ? Integer.MAX_VALUE : A[startOfA + k / 2 - 1]; int halfOfB = startOfB + k / 2 - 1 >= B.length ? Integer.MAX_VALUE : B[startOfB + k / 2 - 1]; if (halfOfA < halfOfB) { return findMedianSortedArraysHelper(A, startOfA + k / 2, B, startOfB, k - k / 2); } else { return findMedianSortedArraysHelper(A, startOfA, B, startOfB + k / 2, k - k / 2); } } }
The complexity is log(k), where k is the kth elements after merged of the two arrays. For this particular problem, the k = (n + m) / 2.
So why the complexity is logk? It's because for each time we can eliminate k/2 data in O(1) time. So overall the complexity is logk.
No comments:
Post a Comment