Leetcode 4. Median of Two Sorted Array
题目
There are two sorted arrays nums1 and nums2 of size x and y respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log(x + y)).
You may assume nums1 and nums2 can not be both empty.
Example 1:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0Example 2:
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5思路
要解决这个问题，我们需要先理解“中位数有什么用？”。在统计学中，中位数用于将集合划分为两个相等长度的子集，一个子集总是大于另一个子集。如果我们理解了中位数对集合的划分，我们就非常接近答案了。
首先，在一个随机的位置paritionX将集合nums1划分为两部分。
leftNums1 | rightNums1
nums1[0], nums1[1], ..., nums1[partitionX-1] | nums1[partitionX], nums1[partitionX+1], ..., nums1[x-1]由于nums1有x个元素，所以就有x+1种分法(partitionX=0~x)。由此可知： len(leftNums1) = partitionX, len(rightNums1) = x - partitionX。 注意：当partitionX = 0时，leftNums1为空，而当paritionX = x时，rightNums1为空。
同理，在一个随机的位置paritionY将长度为y的集合nums2划分为两部分。
leftNums2 | rightNums2
nums2[0], nums2[1], ..., nums2[partitionY-1] | nums2[partitionY], nums2[partitionY+1], ..., nums2[y-1]将 leftNums1 和 leftNums2 放入同一个集合，将 rightNums1 和 rightNums2 放入另外一个集合。 分别称他们为 leftPart 和 rightPart：
leftPart | rightPart
nums1[0], nums1[1], ..., nums1[partitionX-1] (maxLeftX) | nums1[partitionX] (minRightX), nums1[partitionX+1], ..., nums1[x-1]
nums2[0], nums2[1], ..., nums2[partitionY-1] (maxLeftY) | nums2[partitionY] (minRightY), nums2[partitionY+1], ..., nums2[y-1]如果我们能达成两个条件： 1. len(leftPart) = len(rightPart) 2. max(leftPart) <= min(rightPart) 那么我们就能将{nums1, nums2}中所有元素分成两个长度相等的部分，并且其中一部分总是大于另一部分。那么中位数则为：(max(leftPart) + min(rightPart)) / 2.
为了达成这两个条件，我们只需确保： 1. partitionX + partitionY == (x + y + 1) / 2。所有元素被均匀分成两个部分。 2. maxLeftX < minRightY && maxLeftY < minRightX。 因为所有leftNums1一定比rightNums1小，满足以上条件的话leftNums1则同时也比所有的rightNums2小。nums2同理。因此，条件二保证了 leftPart < rightPart。
因此，我们需要在[0, x]区间，用二分搜索法找到partitionX以满足以上两个不等式。我们可以写出以下的伪代码:
<1> 设 low = 0, high = x, 然后在这个区间 [low, high] 中查找 partitionX
<2> 设 partitionX = (low + high)/2, partitionY = (x + y + 1)/2 - partitionX
<3> 此时，我们满足了 len(leftPart)==len(rightPart)， 我们会遇到三种情况：
<a> maxLeftY <= minRightX and maxLeftX <= minRightY
说明我们找到了我们需要的paritionX，停止搜索。我们依据nums1和nums2总数判断:
如果是偶数，leftPart和rightPart数量相等，median = avg(max(maxLeftX, maxLeftY), min(minRightX, minRightY)).
如果是奇数，leftPart多一个元素，则median = avg(maxLeftX, maxLeftY)
<b> maxLeftY > minRightX
意味着 minRightX 太小， 那么我们必须调整 partitionX 以使 `maxLeftY <= minRightX` 仍然成立。
我们可以增大 i吗?
Yes. 因为 partitionX 增大时， partitionY 将减小。
所以 maxLeftY 跟着减小而 minRightX 会增大。maxLeftY <= minRightX就可能成立。
我们可以减小 partitionX 吗?
No! 因为 partitionX 减小时， partitionY 将增大。
所以 maxLeftY 增大而 minRightX 减小。`maxLeftY <= minRightX` 永远不可能成立。
所以我们必须增加partitionX。也就是将搜索范围调整为[partitionX+1, high]。 所以，设 low = partitionX+1, 然后回到步骤 <2>.
<c> maxLeftX > minRightY
意味着 maxLeftX 太大。我们必须减小 partitionX 以使 `maxLeftX<=minRightY`.
就是说我们要调整搜索范围为 [low, partitionX-1].
所以， 设 high = partitionX-1, 然后回到步骤 <2>.我们注意到这里左右切分部分有可能为空。为处理这种特殊情况，我们可以相应的把maxLeft设为Integer.MIN_VALUE、 minRight设为Integer.MAX_VALUE。以下为完整的Java代码。
解答
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
// Ensure nums1 is always the shorter array
if (nums1.length > nums2.length) {
return findMedianSortedArrays(nums2, nums1);
}
int x = nums1.length;
int y = nums2.length;
// Binary Search on partitionX
int low = 0;
int high = x;
while (low <= high) {
// Split the two arrays into four parts st. len(leftX) + len(leftY) = len(rightX) + len(rightY)
int partitionX = low + (high - low) / 2;
int partitionY = (x + y + 1) / 2 - partitionX; // +1 to keep left one more if total is odd
// When left side is emtpy, set maxLeft to MIN_VALUE
// When right side is empty, set minRight to MAX_VALUE
int maxLeftX = (partitionX == 0) ? Integer.MIN_VALUE : nums1[partitionX - 1];
int minRightX = (partitionX == x) ? Integer.MAX_VALUE : nums1[partitionX];
int maxLeftY = (partitionY == 0) ? Integer.MIN_VALUE : nums2[partitionY - 1];
int minRightY = (partitionY == y) ? Integer.MAX_VALUE : nums2[partitionY];
// Condition satisfied: all elements in left part < right part
if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
if ( (x + y) % 2 == 0) // even
return (Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY)) / 2.0;
else // odd: left has extra
return (double) Math.max(maxLeftX, maxLeftY);
}
// maxLeftX too large, Move partitionX to left
else if (maxLeftX > minRightY) {
high = partitionX - 1;
}
// maxLeftX too small so that maxLeftY too large, move partitionX to right
else {
low = partitionX + 1;
}
}
return 0;
}
}Complexity Analysis
Time Complexity: O(log(min(x, y))). 假设
x < y, 那么我们在[0, x]的范围内进行了二分搜索，每次搜索范围会减半，因此我们总共需要log(x)次循环。每次循环仅需constant time。因此总共时间为O(log(min(x, y))).Space Complexity: O(1)。我们并未使用任何额外的空间。
拓展
假设两个input array中有一个没有被
sorted，我们能使用什么办法找到他们的中点呢？
总结
题目中的sorted提示我们使用二分搜索，但我们很难发现如何使用。我们需要对中位数的特性有很强的感知能力，而且需要大量训练锻炼出天才般的敏锐度才能想出这题的解法。 不过，我们可以举一反三，在今后将这个题目的思想应用至其他类似的题目中去。
原文链接
以上解答由下面视频讲解与解答综合得来，有增改。
Last updated
Was this helpful?