題目鏈接：https://leetcode.com/problems/median-of-two-sorted-arrays/
我一直會(huì)卡在這道題上胞锰，在網(wǎng)上看了半個(gè)小時(shí)的博客，愣是沒(méi)看懂唾糯。后來(lái)看到 YouTube 上有一個(gè)印度大哥的講解，豁然開(kāi)朗。
印度大哥的視頻地址：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
題目分析
其實(shí)這道題我卡就卡在，一直沒(méi)有想清楚應(yīng)該如何劃分兩個(gè)數(shù)組迫悠。直接看LeetCode論壇上的答案，也一直沒(méi)有搞懂巩梢。本題只是想求中位數(shù)，并不用管其他的數(shù)字艺玲。
那么核心就在于括蝠，如何劃分兩個(gè)數(shù)組，使得兩個(gè)數(shù)組組合起來(lái)后饭聚，成為一個(gè)在中位數(shù)附近相對(duì)有序的數(shù)組即可忌警。
具體實(shí)例分析
算法分析
定義兩個(gè)變量 partitionX、 partitionY秒梳，分別分割X數(shù)組和Y數(shù)組法绵，記為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)酪碘，這樣數(shù)組就被完整地分成了兩部分朋譬。
如果兩個(gè)數(shù)組長(zhǎng)度的和是奇數(shù)，那么必然是 max(X1, Y1)了兴垦；
如果兩個(gè)數(shù)組長(zhǎng)度的和是偶數(shù)徙赢，那么是 (max(X1, Y1) + min(X2, Y2)) / 2字柠。
代碼實(shí)現(xiàn)
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();
}
總結(jié)
這道題如果能把圖畫(huà)出來(lái)，理解起來(lái)就很容易狡赐。但是這道題在LeetCode中的難度是hard窑业，因?yàn)榫帉?xiě)代碼并不容易，有很多邊界條件：
- 數(shù)組長(zhǎng)度的奇偶
- 移動(dòng)過(guò)程中枕屉，某個(gè)數(shù)組被切割后可能為空
