题目描述
给定两个大小为 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
个人公众号
二进制之路
相关推荐
两个有序数组的中位数。这道题再练习一下。二分搜索,中位数的定义,细节题。 无重复字符的最长子串。滑动窗口常规题,hashmap,记录窗口内每个字符的 ind。 编辑距离。动态规划题。需要再练习 接雨水。单调栈或者两...
两个有序数组的中位数 难的 0005 最长回文子串 中等的 0006 之字形转换 中等的 0007 反转整数 简单的 0008 字符串到整数 (atoi) 中等的 0009 回文数 简单的 0010 正则表达式匹配 难的 0011 盛水最多的容器 中等的 ...
寻找两个正序数组的中位数 7 整数反转 9 回文数 13 罗马数字转整数 14 最长公共前缀 15 三数之和 16 最接近的三数之和 20 有效的括号 21 合并两个有序链表 26 删除排序数组中的重复项 27 移除元素 28 实现strStr 32 ...
求两个排序数组的中位数。 整体运行时间复杂度应该是 O(log (m+n))。 您可以假设 nums1 和 nums2 不能都为空。 例子 nums1 = [1, 3] nums2 = [2] 中位数为 2.0 来源 分解 为了完成这个问题,我使用了以下东西。 类型...
找出两个已排序数组的中位数。 整体运行时间复杂度应该是 O(log (m+n))。 您可以假设 nums1 和 nums2 不能都为空。 例子 示例 1: nums1 = [1, 3] nums2 = [2] 中位数为 2.0 示例 2: nums1 = [1, 2] nums2 = [3, 4]...
两个排序数组的中位数 003 无重复字符的最长子串004 两个数相加005 最长回文子串006之字折线转换(python) 007 反转整数008 字符串到整数(atoi) 009 回文数010* 正则表达式匹配 011-020 011* 最多水的容器012* ...
约瑟夫环 leetcode leetcode 每日一题 8 字符串转换整数 (atoi) 42 接雨水 289 生命游戏(未操作表示状态) 820 字典树 892 数组 正方体表面积 912 数组排序 ...两个栈实现队列 ...最小的k个数 ...在排序数组中查
两个有序数组的中位数 难的 数组、二分查找、分而治之 5 最长回文子串 中等的 细绳 动态规划 6 之字形转换 中等的 细绳 7 反转整数 简单的 数学 8 字符串到整数 (atoi) 中等的 数学,字符串 9 回文数 简单的 数学 11...
加油站 leetcode 大批 第一个缺失阳性(硬) - 最长连续序列(难) - 最大矩形(硬) - 直方图中最大的矩形(硬) ...查找排序数组中元素的第一个和最后一个位置(中) - 查找峰值元素(中) - 位操作 与数组元素的
leetcode寻找最近的 leetcode-with-python3 ...4.寻找两个有序数组的中位数 11.盛最多水的容器 26.删除排序数组中的重复项 15.三数之和 16.最接近的三数之和 27.移除元素 35.搜索插入位置 66.加一 88.合并两个有序数组
0295. 数据流的中位数标签:设计、双指针、数据流、排序、堆(优先队列)难度:困难题目大意要求:设计一个支持一下两种操作的数组结构:void addNum(i
-两个和-https: -买卖股票的最佳时间-https: -包含重复-https: -阵列除自身以外的产品-https: -最大子数组-https: -最大产品子数组-https: - -在旋转的数组排序查找最小 -搜索在旋转的数组排序- -3...
剑指 Offer 41. 数据流中的中位数标签:设计、双指针、数据流、排序、堆(优先队列)难度:困难题目大意要求:设计一个支持一下两种操作的数组结构:void
【两个排序数组的4中位数】很少考 [321 创建最大数] 很少考 [327 范围和的计数] 【289人生游戏】 间隔 [57 插入间隔] [56 次合并间隔] 【252间会议室】 【253会议室二】 [352 作为不相交区间的数据流] TreeMap 柜台 ...
剑指 Offer 41. 数据流中的中位数标签:设计、双指针、数据流、排序、堆(优先队列)难度:困难题目大意要求:设计一个支持一下两种操作的数组结构:void
合并两个排序的链表 二叉树的镜像 打卡第07天[2020-07-13] 对称的二叉树 【自己未解】 调整数组顺序使奇数位于偶数前面 【自己未解】 打卡第08天[2020-07-15] 顺时针打印矩阵 [X] 打卡第09天[2020-07-16] 打印从1到...
寻找两个有序数组的中位数 困难 5 最长回文子串 中等 6 Z 字形变换 中等 7 整数反转 简单 8 字符串转换整数 (atoi) 中等 9 回文数 简单 10 正则表达式匹配 困难 11 盛最多水的容器 中等 12 整数转罗马数字 中等 13 ...
-两个和-https: -买卖股票的最佳时间-https: -包含重复-https: -阵列除自身以外的产品-https: -最大子数组-https: -最大产品子数组-https: - -在旋转的数组排序查找最小 -搜索在旋转的数组排序- -3...
两个有序数组的中位数 难的 005 中等的 006 中等的 007 反转整数 简单的 008 中等的 009 回文数 简单的 010 正则表达式匹配 难的 011 中等的 012 中等的 013 简单的 014 简单的 015 中等的 016 中等的 017 中等的 ...
在旋转排序数组中找到最小值 - 在旋转排序数组中求最小值 II 在旋转排序数组中搜索 - 3总和 - 盛水最多的容器 - 二进制 两个整数之和 - 1 位的数量 - 计数位 - 缺少号码 - 反向位 - 动态规划 爬楼梯 - 硬币变化 - ...