LeetCode 004 Median of Two Sorted Arrays 详细分析
LeetCode 004 Median of Two Sorted Arrays 详细分析
题目链接：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，因为编写代码并不容易，有很多边界条件：
- 数组长度的奇偶
- 移动过程中，某个数组被切割后可能为空