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