来源:力扣(LeetCode)
给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
示例 1:
输入:nums1 = [1,3], nums2 = [2]
输出:2.00000
解释:合并数组 = [1,2,3] ,中位数 2
示例 2:
输入:nums1 = [1,2], nums2 = [3,4]
输出:2.50000
解释:合并数组 = [1,2,3,4] ,中位数 (2 + 3) / 2 = 2.5
提示:
使用二分查找确定两个有序数组的「分割线」,中位数就由分割线左右两侧的元素决定; 分割线满足这样的性质:左右两边元素个数相等(这里忽略两个数组长度之和奇偶性的差异); 分割线左边所有元素 小于等于 分割线右边所有元素; 由于分割线两边元素个数相等,挪动分割线就会有「此消彼长」的现象,因此使用二分去定位。
举个例子
如果题目要我们找的数的范围在 [3..8] ,也就是 3 <= x <= 8,等价于 x >= 3 && x <= 8 。对其中一个条件取反,就可以达到搜索区间的目的。
如果 x < 3,下一轮就应该在 x 的右边继续查找; 如果 x > 8,下一轮就应该在 x 的左边继续查找。
public class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
if (nums1.length > nums2.length) {
int[] temp = nums1;
nums1 = nums2;
nums2 = temp;
}
int m = nums1.length;
int n = nums2.length;
// 分割线左边的所有元素需要满足的个数 m + (n - m + 1) / 2;
int totalLeft = (m + n + 1) / 2;
// 在 nums1 的区间 [0, m] 里查找恰当的分割线,
// 使得 nums1[i - 1] <= nums2[j] && nums2[j - 1] <= nums1[i]
int left = 0;
int right = m;
while (left < right) {
int i = left + (right - left + 1) / 2;
int j = totalLeft - i;
if (nums1[i - 1] > nums2[j]) {
// 下一轮搜索的区间 [left, i - 1]
right = i - 1;
} else {
// 下一轮搜索的区间 [i, right]
left = i;
}
}
int i = left;
int j = totalLeft - i;
int nums1LeftMax = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];
int nums1RightMin = i == m ? Integer.MAX_VALUE : nums1[i];
int nums2LeftMax = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];
int nums2RightMin = j == n ? Integer.MAX_VALUE : nums2[j];
if (((m + n) % 2) == 1) {
return Math.max(nums1LeftMax, nums2LeftMax);
} else {
return (double) ((Math.max(nums1LeftMax, nums2LeftMax) + Math.min(nums1RightMin, nums2RightMin))) / 2;
}
}
}
本来是使用归并排序的,但这种方法的时间复杂度为O(m+n)O(m+n) 不满足题目O(log (m+n))O(log(m+n))的要求,所以使用二分查找来解题