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
Tags: Array, Binary Search, Divide and Conquer
题意是给你两个已排序的递增数组，让你找出其中位数，乍一看这题并不是很难，其实这题难度不可小觑，要做出时间复杂度为O(log (m+n))的话需要了解从两个递增数组中找出第k大的元素，也就是我写的helper函数所起到的作用。下面来解释以下其原理：假设数组分别记为A，B，当前需要搜索第k大的数，于是我们可以考虑从数组A中取出前m个元素，从数组B中取出k-m个元素。由于数组A，B分别排序，则A[m]大于从数组A中取出的其他所有元素，B[k-m] 大于数组B中取出的其他所有元素。此时，尽管取出元素之间的相对大小关系不确定，但A[m]与B[k-m]的较大者一定是这k个元素中最大的。那么，较小的那个元素一定不是第k大的，它至多是第k-1大的：因为它小于其他未被取出的所有元素，并且小于取出的k个元素中最大的那个。为叙述方便，假设A[m]是较小的那个元素。那么，我们可以进一步说，A[1], A[2]…A[m-1]也一定不是第k大的元素，因为它们小于A[m]，而A[m]至多是第k-1大的。因此，我们可以把较小元素所在数组中选出的所有元素统统排除，并且相应地减少k值。这样，我们就完成了一次范围缩小。特别地，我们可以选取m=k/2。而本题只是其一种情况而已，也就当总长为偶数时，找出其中间的两个数，相加除二即可；当总长为奇数时，找到中间的数即可。
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int len = nums1.length + nums2.length;
if (len % 2 == 0) {
return (helper(nums1, 0, nums2, 0, len / 2) + helper(nums1, 0, nums2, 0, len / 2 + 1)) / 2.0;
}
return helper(nums1, 0, nums2, 0, (len + 1) / 2);
}
private int helper(int[] nums1, int m, int[] nums2, int n, int k) {
if (m >= nums1.length) return nums2[n + k - 1];
if (n >= nums2.length) return nums1[m + k - 1];
if (k == 1) return Math.min(nums1[m], nums2[n]);
int p1 = m + k / 2 - 1;
int p2 = n + k / 2 - 1;
int mid1 = p1 < nums1.length ? nums1[p1] : Integer.MAX_VALUE;
int mid2 = p2 < nums2.length ? nums2[p2] : Integer.MAX_VALUE;
if (mid1 < mid2) {
return helper(nums1, m + k / 2, nums2, n, k - k / 2);
}
return helper(nums1, m, nums2, n + k / 2, k - k / 2);
}
}如果你同我一样热爱数据结构、算法、LeetCode，可以关注我GitHub上的LeetCode题解：awesome-java-leetcode