@Yano
2018-11-24T15:10:26.000000Z
字数 1791
阅读 2120
LeetCode
题目链接:https://leetcode.com/problems/median-of-two-sorted-arrays/
我一直会卡在这道题上,在网上看了半个小时的博客,愣是没看懂。后来看到 YouTube 上有一个印度大哥的讲解,豁然开朗。
印度大哥的视频地址:Binary Search : Median of two sorted arrays of different sizes.
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)).
You may assume nums1 and nums2 cannot be both empty.
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
其实这道题我卡就卡在,一直没有想清楚应该如何划分两个数组。直接看LeetCode论坛上的答案,也一直没有搞懂。本题只是想求中位数,并不用管其他的数字。
那么核心就在于,如何划分两个数组,使得两个数组组合起来后,成为一个在中位数附近相对有序的数组即可。
定义两个变量 partitionX、 partitionY,分别分割X数组和Y数组,记为X1, X2, Y1, Y2。使得
len(X1) + len(Y1) == len(X2) + len(Y2)
或
len(X1) + len(Y1) == len(X2) + len(Y2) + 1
并且使得 max(X1) < min(Y2), max(Y1) < min(X2),这样数组就被完整地分成了两部分。
如果两个数组长度的和是奇数,那么必然是 max(X1, Y1)了;
如果两个数组长度的和是偶数,那么是 (max(X1, Y1) + min(X2, Y2)) / 2。
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
if (nums1.length > nums2.length) {
return findMedianSortedArrays(nums2, nums1);
}
int x = nums1.length, y = nums2.length;
int low = 0, high = x;
while (low <= high) {
int partitionX = (low + high) / 2;
int partitionY = (x + y + 1) / 2 - partitionX;
int maxLeftX = (partitionX == 0) ? Integer.MIN_VALUE : nums1[partitionX - 1];
int maxLeftY = (partitionY == 0) ? Integer.MIN_VALUE : nums2[partitionY - 1];
int minRightX = (partitionX == x) ? Integer.MAX_VALUE : nums1[partitionX];
int minRightY = (partitionY == y) ? Integer.MAX_VALUE : nums2[partitionY];
if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
if ((x + y) % 2 == 0) {
return (Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY)) / 2.0;
} else {
return Math.max(maxLeftX, maxLeftY);
}
} else if (minRightX < maxLeftY) {
low = partitionX + 1;
} else {
high = partitionX - 1;
}
}
throw new RuntimeException();
}
这道题如果能把图画出来,理解起来就很容易。但是这道题在LeetCode中的难度是hard
,因为编写代码并不容易,有很多边界条件:
1. 数组长度的奇偶
2. 移动过程中,某个数组被切割后可能为空