魏县网站建设,做废钢推广网站,晋城网站建设电话,福田做棋牌网站建设找哪家效益快文章目录 [toc]题目描述样例输入输出与解释样例1样例2 提示Python实现二分查找划分数组 个人主页#xff1a;丷从心
系列专栏#xff1a;LeetCode
刷题指南#xff1a;LeetCode刷题指南 题目描述
给定两个大小分别为m和n的正序#xff08;从小到大#xff09;数组nums1… 文章目录 [toc]题目描述样例输入输出与解释样例1样例2 提示Python实现二分查找划分数组 个人主页丷从心·
系列专栏LeetCode
刷题指南LeetCode刷题指南 题目描述
给定两个大小分别为m和n的正序从小到大数组nums1和nums2请找出并返回这两个正序数组的中位数算法的时间复杂度应该为O(log (mn)) 样例输入输出与解释
样例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 提示
nums1.length mnums2.length n0 m 10000 n 10001 m n 2000-10^6 nums1[i], nums2[i] 10^6 Python实现
二分查找
class Solution:def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) - float:def getKthElement(k):index1, index2 0, 0while True:# 特殊情况if index1 m:return nums2[index2 k - 1]if index2 n:return nums1[index1 k - 1]if k 1:return min(nums1[index1], nums2[index2])# 正常情况new_index1 min(index1 k // 2 - 1, m - 1)new_index2 min(index2 k // 2 - 1, n - 1)pivot1, pivot2 nums1[new_index1], nums2[new_index2]if pivot1 pivot2:k - new_index1 - index1 1index1 new_index1 1else:k - new_index2 - index2 1index2 new_index2 1m, n len(nums1), len(nums2)total_length m nif total_length % 2 1:return getKthElement((total_length 1) // 2)else:return (getKthElement(total_length // 2) getKthElement(total_length // 2 1)) / 2 划分数组
class Solution:def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) - float:if len(nums1) len(nums2):return self.findMedianSortedArrays(nums2, nums1)inf 10 ** 6m, n len(nums1), len(nums2)left, right 0, mwhile left right:i (left right) // 2j (m n 1) // 2 - inums_im1 (-inf if i 0 else nums1[i - 1])nums_i (inf if i m else nums1[i])nums_jm1 (-inf if j 0 else nums2[j - 1])nums_j (inf if j n else nums2[j])if nums_im1 nums_j:left i 1median1, median2 max(nums_im1, nums_jm1), min(nums_i, nums_j)else:right i - 1return (median1 median2) / 2 if (m n) % 2 0 else median1
