首页 > 代码库 > logn+m复杂度找两个有序数列的中位数
logn+m复杂度找两个有序数列的中位数
class Solution { public: double fun(vector<int> nums1,int n,vector<int> nums2,int m,int k) { if(nums1.size()-n>nums2.size()-m) return fun(nums2,m,nums1,n,k); if(n==nums1.size()) return nums2[k-1+m]; if(k==1) return min(nums1[n],nums2[m]); int pa=min(k/2,(int)nums1.size()-n),pb=k-pa; if(nums1[pa-1+n]<nums2[pb-1+m]) return fun(nums1,n+pa,nums2,m,k-pa); if(nums1[pa-1+n]>nums2[pb-1+m]) return fun(nums1,n,nums2,m+pb,k-pb); return nums1[pa-1+n]; } double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { int tot=nums1.size()+nums2.size(); if(tot&1) return fun(nums1,0,nums2,0,tot/2+1); return (fun(nums1,0,nums2,0,tot/2)+fun(nums1,0,nums2,0,tot/2+1))/2; } };
logn+m复杂度找两个有序数列的中位数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。