Leetcode-计算两个排序数组的中位数
题目描述
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。
请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n)) 。
示例 1:
nums1 = [1, 3]
nums2 = [2]中位数是 2.0
示例 2:
nums1 = [1, 2]
nums2 = [3, 4]中位数是 (2 + 3)/2 = 2.5
算法实现
我的实现思路
- 根据元素总个数，计算出中位数的位置。
- 如果总个数为奇数，则中位数取中间一个即可。
- 如果总个数为偶数，则需要取中间两个数之和的平均值。
- 假设桌上有两副已排好序的扑克牌，从上到下由小到大排序。那么
- 从两副牌的顶部各取一张，进行比较后取最小的一张牌。
- 从取出最小牌的那副再取一张，与另一副前一次抽取的牌进行比较，然后取最小的一张牌。
- 如此循环，我们拿到的牌将是从小到大的顺序，直至拿到牌的数量与我们要找的中位数位置相同即可停止。
- 此时，如果判断元素总数为偶数个，则再取一张牌后停止。
- 最后，如果是奇数个元素，则直接返回。如果是偶数个元素，则返回两个数之和的平均值。
/**
* 个人实现版本.
*
* @param nums1
* @param nums2
* @return
*/
public static double findMedianSortedArraysV1(int[] nums1, int[] nums2) {
int[] resultArray = new int[2];
int idx1 = 0;
int idx2 = 0;
int currentCount = 0;
int size1 = (nums1 == null) ? 0 : nums1.length;
int size2 = (nums2 == null) ? 0 : nums2.length;
boolean evenResult = true; // 总数是否为偶数个
int medianNum = (size1 + size2) / 2; // 中位数的位置
if ((size1 + size2) % 2 != 0) {
medianNum++;
evenResult = false; // 总数为奇数个
}
if (medianNum == 0) {
throw new IllegalArgumentException("median num not found");
}
int currentValue = 0;
while (true) {
if (idx1 <= size1 - 1 && idx2 <= size2 - 1) {
if (nums1[idx1] <= nums2[idx2]) {
currentValue = nums1[idx1++];
} else {
currentValue = nums2[idx2++];
}
currentCount++;
} else if (idx1 <= size1 - 1) {
currentValue = nums1[idx1++];
currentCount++;
} else if (idx2 <= size2 - 1) {
currentValue = nums2[idx2++];
currentCount++;
}
// 相等则找到中位数
if (currentCount == medianNum) {
resultArray[0] = currentValue;
if (!evenResult) { // 如果总数为偶数，需要找到中间的2个数取平均值
break;
}
} else if (currentCount > medianNum && evenResult) { // 找到第二数
resultArray[1] = currentValue;
break;
}
}
double resultValue = evenResult ? Double.valueOf(resultArray[0] + resultArray[1]) / 2 : Double.valueOf(resultArray[0]);
return resultValue;
}
个人实现的版本，时间复杂度为O((m+n)/2)，比题目的要求慢一些，不过思路相对清晰一些。
习题答案
个人理解如下：
假设有数组A，长度为m，任意位置i将数组分为左右两部分。数组B，长度为n，任意位置j将数组分为左右两部分。
那么i>=0，且i<=m。j>=0，且j<=n。i和j可以理解为数组从小到大的第几个数，例如i=1代表A[0]，即数组A的第一个数。
如果要找到A和B各自的中位数，需要满足i=m-i，j=n-j，即左右两部分的个数是相同的，此时中间的数即为中位数。当然，实现的时候仍需要考虑奇数、偶数个数组元素的问题。
由于我们是在A和B两个数组合并之后找中位数，因此找到中位数需要满足i+j=m-i+n-j（或：m-i+n-j+1，奇数个元素的情况）。
另外，题目要求的时间复杂度是log(m+n)，所以很容易想到二分查找（如折半查找、二叉查找树）。所以问题的关键点就是，在不合并数组并做好排序（时间复杂度为O(m)、O(n)或O(m+n)，肯定不满足需求）的情况下，如何利用二分查找来实现该算法。
由前面我们推导出的公式可知，j=(m+n)/2-i或j=(m+n+1)/2-i。
事实上，如果要简单的理解可以不用这么麻烦的推导。
假设数组元素的总个数为奇数，那么中位数必然在第(m + n + 1) / 2个。
此时，要找到中位数，显然i+j=(m + n + 1) / 2，这个结果与上述的推导是一致的。有了这个公式，二分查找就好办了。分而治之，先计算出数组A的中间位置i=(0+m)/2。那么，此时j就可以通过前面的公式计算出来了。
二分查找时，如果满足B[j−1]<=A[i]且A[i−1]<=B[j]，则表示找到中位数了，结束查找。如果不满足，则在i的前或后半部分继续进行上述的二分查找，直至满足条件即可。
为什么说满足B[j−1]<=A[i]且A[i−1]<=B[j]，则表示找到中位数了？
因为A[i−1]+B[j−1]代表数组的一半元素，共有i+j个。那么只要满足最后一个条件，我们就找到中位数了。最后一个条件，就是A[i−1]和B[j−1]都要小于等于另一半元素的值，这里我们只要保证同时小于另一半的最小值A[i]和B[j]（或者说是下一个值）即可。
/**
* 习题答案
*
* @param A
* @param B
* @return
*/
public double findMedianSortedArrays(int[] A, int[] B) {
int m = A.length;
int n = B.length;
if (m > n) { // to ensure m<=n
int[] temp = A; A = B; B = temp;
int tmp = m; m = n; n = tmp;
}
int iMin = 0, iMax = m, halfLen = (m + n + 1) / 2;
while (iMin <= iMax) {
int i = (iMin + iMax) / 2;
int j = halfLen - i;
if (i < iMax && B[j-1] > A[i]){
iMin = iMin + 1; // i is too small
}
else if (i > iMin && A[i-1] > B[j]) {
iMax = iMax - 1; // i is too big
}
else { // i is perfect
int maxLeft = 0;
if (i == 0) { maxLeft = B[j-1]; }
else if (j == 0) { maxLeft = A[i-1]; }
else { maxLeft = Math.max(A[i-1], B[j-1]); }
if ( (m + n) % 2 == 1 ) { return maxLeft; }
int minRight = 0;
if (i == m) { minRight = B[j]; }
else if (j == n) { minRight = A[i]; }
else { minRight = Math.min(B[j], A[i]); }
return (maxLeft + minRight) / 2.0;
}
}
return 0.0;
}
算法实现
https://github.com/qiuzj/leetcode/blob/master/src/main/java/cn/javaee/leetcode/q4/median_of_two_sorted_arrays/MedianOfTwoSortedArrays.java
https://leetcode-cn.com/problems/median-of-two-sorted-arrays/description/
转载请注明来源：http://zhanjia.iteye.com/blog/2427289
个人公众号
二进制之路