知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 57 - 寻找两个正序数组的中位数 ## 题目(LeetCode 4) 给定两个正序数组,找出中位数,要求 O(log(m+n))。 ## 解法:二分查找 ```java class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1); int m = nums1.length, n = nums2.length; int lo = 0, hi = m; while (lo <= hi) { int i = (lo + hi) / 2; int j = (m + n + 1) / 2 - i; int maxLeft1 = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1]; int minRight1 = (i == m) ? Integer.MAX_VALUE : nums1[i]; int maxLeft2 = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1]; int minRight2 = (j == n) ? Integer.MAX_VALUE : nums2[j]; if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) { if ((m + n) % 2 == 1) return Math.max(maxLeft1, maxLeft2); return (Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) / 2.0; } else if (maxLeft1 > minRight2) hi = i - 1; else lo = i + 1; } return 0; } } ``` ## 复杂度 - 时间 O(log(min(m,n))),空间 O(1) ## 一句话总结 在较短数组上二分,找到一个分割使左半部分最大值 ≤ 右半部分最小值。 ## 说明 寻找两个正序数组的中位数要求 O(log(m+n)),这决定了**必须用二分查找**。 暴力合并后取中位数是 O(m+n),不满足要求。当前二分解法已是最优,核心思路是在较短数组上二分,找到一个分割点使得左半部分的最大值 ≤ 右半部分的最小值。
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入