前端宝藏知识
第四题：寻找两个正序数组的中位数
难度：困难
 
题目描述：
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
示例 1：
输入：nums1 = [1,3], nums2 = [2] 输出：2.00000 解释：合并数组 = [1,2,3] ，中位数 2 示例 2：
输入：nums1 = [1,2], nums2 = [3,4] 输出：2.50000 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
题目解答：
要找到两个正序数组的中位数，并且算法时间复杂度要求为 O(log (m+n))，可以借助于二分查找的思想来解决。
解题思路：
1. 理解中位数的性质： 对于一个有序数组，中位数是数组中间的数（如果数组长度为偶数，则是中间两个数的平均值）。
2. 二分查找的应用：
• 我们可以通过二分查找来确定在第一个数组 nums1 中取多少个元素作为左半部分，从而确定第二个数组 nums2 中需要取多少个元素作为右半部分。
• 由于 nums1 和 nums2 都是有序的，左半部分的最大值和右半部分的最小值就是我们需要比较的关键点。
3. 具体步骤：
• 设定二分查找的边界 left 和 right，其中 left = 0，right = m（假设 m <= n，保证 nums1 是较短的数组）。
• 在 nums1 中取 i 个元素作为左半部分，那么在 nums2 中应该取 (m + n + 1) / 2 - i 个元素作为右半部分（保证左右两部分的元素个数相等或左边多一个）。
• 然后进行二分查找，调整 left 和 right，直到找到符合条件的 i。
4. 边界处理： 特别是在处理边界条件时要注意，例如当 i 达到 m 时，左半部分已经取完了所有的 nums1，或者 i 为 0 时，左半部分为空。
5. 计算中位数： 找到合适的 i 后，根据左半部分的最大值、右半部分的最小值计算中位数。
 
 
JavaScript 实现：
解释：
这段代码通过二分查找的方式，高效地找到了两个有序数组的中位数。关键是在每一步中，通过比较两个数组中的元素，动态调整二分查找的范围，直到找到合适的划分点。
 
2024-07-09
浏览85
力扣算法题
登录后评论
评论
分享