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

杂谈:

题目不难,最好想的当然是类似归并排序,也就是每次从nums1和nums2中拿一个更小的,直到某一个为空,或者找到了中间那个数(nums1.size()+nums2.size())/2

这里主要记录一下官解给出的另外两种对数级的算法,主要是尝试用一个解题人的思想来理解算法

法一: 比较第k大,每次舍一半 O(log(m+n))

我们取两个序列中第 k/2-1 大的元素,nums1的记为a,nums2的记为b,不妨设a<=b,又由于两个序列都是正序的,所以比a小的只可能是 nums1中0...k/2-2 和 nums2中0...k/2-2,这一共是 k/2-1 + k/2-1 <= k-2,也就是说a最大是第k-1大,也就说明a和它前面的那些元素都可以被舍弃.

而当一个序列为空,直接返回另一个序列按序的指定元素即可, 因为我们每次舍弃k/2-1个,而当一个序列为空,就直接找到所求元素了,所以时间复杂度是O(log(m+n))

参考代码如下:

class Solution {
public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {//法一: 归并排序 O(m+n)//法二: 删除小者的那一半log(m+n)//法三: m<n 对[0,m-1]做一个二分查找int m=nums1.size(),n=nums2.size();int k=(m+n+1)/2;//// 0...k/2-2,k/2-1...m-1   0...k/2-2,k/2-1...n-1// 所以对于nums1[k/2-1]和nums2[k/2-1]的小者,记为a//   至多只有 nums1的0...k/2-2 和 nums2的0...k/2-2 共 k/2-1 + k/2-1 <= k-2 个数,// 所以a至多是第k-1小,而中位数(第k小,前面一共k-1个数)也不会被误删auto ans=findKth(nums1,nums2,k,0,0);return (m+n)%2?ans.first:(ans.first+ans.second)*1.0/2;}
//我们直接同时取到 第k大 和 第k+1大pair<int,int> findKth(vector<int>& nums1,vector<int>& nums2,int k,int index1,int index2){if(index1>=nums1.size()){//nums1为空if(index2+k<nums2.size()){return {nums2[index2+k-1],nums2[index2+k]};}else{return {nums2[index2+k-1],INT_MAX};}}if(index2>=nums2.size()){//nums2为空if(index1+k<nums1.size()){return {nums1[index1+k-1],nums1[index1+k]};}else{return {nums1[index1+k-1],INT_MAX};}}if(k==1){// 12都非空,但是k=1了int first=INT_MAX,second=INT_MAX;if(nums1[index1]<=nums2[index2]){first=nums1[index1];second=nums2[index2];if(index1+1<nums1.size()) second=min(second,nums1[index1+1]);}else{first=nums2[index2];second=nums1[index1];if(index2+1<nums2.size()) second=min(second,nums2[index2+1]);}return {first,second};}int k1=k/2-1;int tmp1=INT_MAX,tmp2=INT_MAX;int cut1,cut2;//cut1 和 cut2是删除的个数if(index1+k1<nums1.size()){tmp1=min(tmp1,nums1[index1+k1]);cut1=k/2;}else{cut1=nums1.size()-index1;}if(index2+k1<nums2.size()){tmp2=min(tmp2,nums2[index2+k1]);cut2=k/2;}else{cut2=nums2.size()-index2;}if(tmp1<=tmp2){//比较这次选中的 两个元素return findKth(nums1,nums2,k-cut1,index1+cut1,index2);}else{return findKth(nums1,nums2,k-cut2,index1,index2+cut2);}}
};

法二: 根据中位数的定义

我们找一个i,把nums1分成两部分, nums1[0...i-1](i个) 和 nums[i...m-1](m-i个),我们找一个j,同样把nums2分成两部分,nums2[0...j-1](j个) 和 nums[j...n-1](n-j个),如果能够使得前面(i+j) 个和后面(m-i+n-j)个满足中位数的定义,就是了

如果m+n是偶数,我们就找 i+j=m-i + n-j 同时使得

nums1[i-1]<=nums[j] && nums2[j-1]<=nums1[i]

如果m+n是奇数,我们就找 i+j=m-i + n-j +1 同时使得

nums1[i-1]<=nums[j] && nums2[j-1]<=nums1[i]

统一一下就是 i+j = (n+m+1)/2

那也就是找 i,j 使得 i+j = (n+m+1)/2 同时 nums1[i-1]<=nums[j] && nums2[j-1]<=nums1[i]

这个命题等价于寻找最大的 i 使得满足 i+j = (n+m+1)/2 同时 nums1[i-1]<=nums2[j], 简单证一下:

首先说明存在, 随着i增大 nums1[i-1]增大 nums2[j]下降,所以会存在一个最大的i满足上式

既然是最大的i那就说明,对i+1上式不成立, 也就是说(i+1) + (j-1) = (n+m+1)/2 而nums1[i] > nums2[j-1],也就是nums2[j-1]<nums1[i],甚至比原命题更强

同时对于边界,我们取nums1[-1]=nums2[-1]=INT_MIN,nums1[n]=nums2[m]=INT_MAX,这样保障即使边界也是能正确取值的

参考代码如下:

class Solution {
public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {//法一: 归并排序 O(m+n)//法二: 删除小者的那一半log(m+n)//法三: m<n 对[0,m-1]做一个二分查找if(nums2.size()<nums1.size()){return findMedianSortedArrays(nums2,nums1);}//现在nums1是元素个数更少的了//0...i-1  |  i...m-1//0...j-1  |  j...n-1//i+j = n-i +m-j  ||  i+j = n-i +m-j+1 (或者左边多一个元素,所以是等于右边+1)  -> //我们要求出来最大的i, 使得nums1[i-1]<nums2[j],nums2[j-1]<nums1[i]int m=nums1.size(),n=nums2.size();int l=0,r=nums1.size();int median1=INT_MIN,median2=INT_MIN;while(l<=r){int mid=(r-l)/2+l;int i=mid;int j=(m+n+1)/2-i;int nums1_i1=i==0?INT_MIN:nums1[i-1];int nums1_i =i==m?INT_MAX:nums1[i];int nums2_j1=j==0?INT_MIN:nums2[j-1];int nums2_j =j==n?INT_MAX:nums2[j];if(nums1_i1<=nums2_j){median1=max(nums1_i1,nums2_j1);median2=min(nums1_i, nums2_j);l=mid+1;}else{r=mid-1;}}return (m+n)%2?median1:(median1+median2)/2.0;}
};