O.o?4月前
两数组中位数:二分查找法 本视频讲解力扣(LeetCode)第4题“寻找两个正序数组的中位数”。 【问题描述】 给定两个大小分别为 `m` 和 `n` 的 **正序(非递减)** 数组 `nums1` 和 `nums2`。请找出这两个正序数组的 **中位数**。要求算法的时间复杂度为 **O(log(m+n))**。 【关键示例】 输入:nums1 = [1, 3], nums2 = [2] 输出:2.00000 解释:合并数组 = [1, 2, 3],中位数是 2。 【核心挑战】 在 O(log(m+n)) 的时间限制下,不能直接合并数组。这要求我们必须在两个数组上进行某种形式的 **二分查找**。 【解题要点】 1️⃣ **核心思路转换**:将寻找中位数转换为寻找两个数组中第 k 小的数,或找到将两个数组划分为左右两部分的正确分割线。 2️⃣ **对短数组二分**:始终在较短的数组上进行二分搜索,确定其分割点 `i`,则较长数组的分割点 `j` 可根据中位数位置公式 `(m+n+1)/2 - i` 得出。 3️⃣ **检查分割有效性**:有效的分割应满足:`nums1`左半部最大值 <= `nums2`右半部最小值,且 `nums2`左半部最大值 <= `nums1`右半部最小值。这保证了左半部分的所有元素都小于等于右半部分。 4️⃣ **处理边界情况**:使用 `INT_MIN` 和 `INT_MAX` 来优雅地处理数组分割到最左或最右时,左半部为空或右半部为空的情况。 【时间复杂度】 O(log(min(m, n))),因为我们只在较短的数组上进行二分搜索。 💡 记住:将复杂问题(中位数)转化为等价且可二分查找的问题(有序数组的分割),是解决此类难题的关键! 【免责声明】 本文内容仅为编程学习交流,题目来源于公开的编程练习平台。分享的解题思路为个人学习总结,仅供参考。如涉及版权问题,请联系删除。 #编程 #学习 #算法 #合集
00:00 / 02:01
连播
清屏
智能
倍速
点赞3
00:00 / 01:02
连播
清屏
智能
倍速
点赞62
00:00 / 03:19
连播
清屏
智能
倍速
点赞2
00:00 / 00:36
连播
清屏
智能
倍速
点赞0
00:00 / 03:10
连播
清屏
智能
倍速
点赞9085
00:00 / 02:41
连播
清屏
智能
倍速
点赞938
00:00 / 04:30
连播
清屏
智能
倍速
点赞26
00:00 / 00:38
连播
清屏
智能
倍速
点赞1142
00:00 / 03:05
连播
清屏
智能
倍速
点赞70
00:00 / 04:01
连播
清屏
智能
倍速
点赞5