leetcode热题100.寻找两个正序数组中的中位数

本文主要是介绍leetcode热题100.寻找两个正序数组中的中位数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem: 4. 寻找两个正序数组的中位数

题目

给定两个大小分别为 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

思路

定义numus1为较小数组，nums2为较大数组
假设有一条分界线在两个数组nums1和nums2中
这个分界线满足两个条件：

性质1：

根据这一性质，我们定义分界线左边的元素个数，可以只二分小的那个nums就可以确定分割线的位置

性质2：

根据这一性质，我们可以写出二分搜索的判断条件，即左上>右下或者左下>右上都不符合我们的分界线要求

我们发现数组下标i就是nums1分割线左边的元素个数，那么同理 total_left-i 就是nums2分割线右边的元素的位置

我们同时要考虑边界情况，如果 i=0 或者 i=m 或者 j=0 或者 j = n的情况，我们将他们取一个极大的数或者极小的数，为什么这样取，读者可以看最终返回的答案的规则

关于最后的答案，如果 m+n 是奇数，我们只需要取nums1和nums2的分界线左边最大点即可；如果 m + n 是偶数，我们需要取得分界线左边的最大值和分界线右边的最小值的和的二分之一。

复杂度

时间复杂度:

$O(log(min(m,n))$

空间复杂度:

$O(1)$

Code

class Solution:def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:# nums1 是较小的数组，nums2是较大的数组if len(nums1) > len(nums2):nums1,nums2 = nums2,nums1m = len(nums1)n = len(nums2)total_left = (m+n+1) // 2# 从小的数组nums1开始二分left = 0rigth = mwhile left<rigth:i = (left+rigth+1) // 2 # nums1的分界线的右边的节点j = total_left - i  # nums2的分界线的右边的节点if nums1[i-1] > nums2[j]: # nums1分界线左边的点小于nums2分界线右边的点rigth = i-1else:left = ii = leftj = total_left - i# 处理边界情况nums1_left = nums1[i-1] if i>0 else float('-inf')nums1_right = nums1[i] if i<m else float('inf') nums2_left = nums2[j-1] if j>0 else float('-inf')nums2_right = nums2[j] if j<n else float('inf')if (m+n) % 2 == 1: # 如果 m+n 是奇数，我们只需要取nums1和nums2的分界线左边最大点即可return max(nums1_left,nums2_left)else: # 如果 m + n 是偶数，我们需要取得分界线左边的最大值和分界线右边的最小值的和的二分之一return (max(nums1_left,nums2_left)+min(nums1_right,nums2_right)) / 2

这篇关于leetcode热题100.寻找两个正序数组中的中位数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---