给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。 请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。 你可以假设 nums1 和 nums2 不会同时为空。
2024-09-03 16:54:58
class Solution {
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 = i + 1; // i is too small
}
else if (i > iMin && A[i-1] > B[j]) {
iMax = i - 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;
}
}
最新文章
- Intellij IDEA常用快捷键——Mac版
- (转)最强Android模拟器genymotion的安装与配置
- android 运行 python
- <;Chapter 2>;2-2-2.开发Python应用(Developing a Python App)
- SQL Server调优系列进阶篇 - 如何重建数据库索引
- vc笔记六
- Gulp-自动化编译sass和pug文件
- bootstrap表格添加按钮、模态框实现
- 【转载】Window服务器开机后一直处于蓝色屏幕(非蓝屏 crash)状态
- java30
- bzoj1741 [Usaco2005 nov]Asteroids 穿越小行星群 最小点覆盖
- URAL 1004 Sightseeing Trip(floyd求最小环+路径输出)
- ASP.NET AJAX入门系列(1):概述
- spring 代理注解 <;aop:aspectj-autoproxy />;
- Unity绘制Png图片
- 二叉树—-1(No.9HN省赛小题)
- php取两个整数的最大公约数算法大全
- db2 托管事务未设置方法有问题
- Codeforces 632D Longest Subsequence 2016-09-28 21:29 37人阅读 评论(0) 收藏
- DAG最长路径
热门文章
- gunicorn+nginx配置方法
- Python学习之==>;线程&;&;进程
- delphi2010:按键 控制键 组合键的判断 响应
- window.screenLeft&;&;window.screenTop&;&;window.screenX&;&;window.screenY
- paramiko远程连接linux服务器进行上传下载文件
- yum安装php7
- cdh平台问题
- 剑指Offer编程题(Java实现)——删除链表中重复的结点
- 04: DjangoRestFramework使用
- Runnable、Callable和Future三者对比