当前位置: 首页 > 科技观察

LeetCode-求两个排序数组的中值

时间:2023-03-13 11:33:03 科技观察

前言我们社区会继续介绍谷一(Netflix增长黑客,《iOS 面试之道》作者,ACE职业健身教练。微博:@古迪道长[1])的解法为了方便大家学习阅读,将Swift算法题整理成了文字版。到目前为止,我们已经更新了3期的LeetCode算法。我们会保持更新时间和进度(周一、周三、周五上午9:00发布)。每期内容不多。希望大家在上班的路上读一读,积累久了会有很大的提升。该算法的解法github仓库地址为:https://github.com/soapyigu/LeetCode-Swift[2]不积步难行千里;如果您有建议和意见,请在文末留言,我们将尽力满足您的需求。难度级别:难度描述给定两个有序数组nums1和nums2,它们的数据长度分别为n和m,将两个数组合并成一个新数组,并返回新数组的中间值。整体运行时间复杂度应为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],中位数valueFor(2+3)/2=2.5示例3输入:nums1=[0,0],nums2=[0,0]输出:0.00000示例4输入:nums1=[],nums2=[1]输出:1.00000示例5输入:nums1=[2],nums2=[]输出:2.00000limitnums1.length==mnums2.length==n0<=m<=10000<=n<=10001<=m+n<=2000-106<=nums1[i],nums2[i]<=106答案classSolution{funcfindMedianSortedArrays(_nums1:[Int],_nums2:[Int])->Double{letm=nums1.countletn=nums2.countifm>n{returnfindMedianSortedArrays(nums2,nums1)}varhalfLength:Int=(m+n+1)>>1varb=0,e=mvarmaxOfLeft=0varminOfRight=0whileb<=e{letmid1=(b+e)>>1letmid2=halfLength-mid1ifmid1>0&&mid2nums2[mid2]{e=mid1-1}elseifmid2>0&&mid1