leetcode 4. 寻找两个正序数组的中位数[二分查找]

系统管理员 2022-10-23 12:45 12阅读 0赞

> 其实就是找到两个数组中第k大的数  
> 每次一k/2的复杂度缩小  
> 排除k/2个不可能的数  
> 复杂度log(m+n)

class Solution { 
    public:
        double findMedianSortedArrays(vector<int>& a, vector<int>& b) { 
            int m = a.size();
            int n = b.size();
            int cnt = m+n;
            if( cnt%2==1  ){ 
                return findk(a,b,(cnt+1)/2 );
            }else{ 
                return (findk(a,b,cnt/2) +findk(a,b,cnt/2+1))/2.0 ;
            }
            return 0; 
        }
        
        int findk(vector<int>& a, vector<int>& b,int k){ 
            
            int m = a.size();
            int n = b.size();
            
            int ai = 0;
            int bi = 0;
            
            while(true){ 
                
                if(ai==m){ 
                    return b[bi+k-1];  
                }
                if(bi==n){ 
                    return a[ai+k-1];
                }
                
                if(k==1){ 
                    return min( a[ai],b[bi] );
                }
                
                int ani = min(ai+k/2-1,m-1);
                int bni = min(bi+k/2-1,n-1);
                
                if(a[ani] <= b[bni]){ 
                    k -= ani - ai + 1;
                    ai = ani + 1;
                }else{ 
                    k -= bni - bi + 1;
                    bi = bni + 1;
                }
            }
        }
    };

> 长度分别为m和n的两个序列  
> 从两个序列中各自画一条线一分为二  
> 将两个序列左边的个数相加，中位数就是找到(m+n+1)/2,  
> 奇数是左边多一个，偶数的时候一样多  
> 因为知道了总数，所有只在较短的数组进行二分查找即可  
> 较长的数组的切割位置就是确定的（因为两个序列总的长度固定）  
> 找到满足第一个序列切割位置左边的最大值小于第二个序列切割位置的最小值的位置  
> 将第一个序列的切割位置尽量向右推，最右时候就是答案  
> 复杂度log(min(m,n))

class Solution { 
    public:
        double findMedianSortedArrays(vector<int>& a, vector<int>& b) { 
            if(a.size() > b.size()){ 
                swap(a,b);
            }
            int m = a.size();
            int n = b.size();
            int lcnt = (m+n+1)/2;
            int l = 0;
            int r = m;
            //a[i-1]<b[j] && b[j-1]<a[i]
            
            int lmax = INT_MIN;
            int rmin = INT_MAX;
            
            while(l<=r){ 
                int i = (l+r+1)/2;
                int j = lcnt -i;
                
                int ai_1 = (i==0?INT_MIN:a[i-1]);
                int ai = (i==m?INT_MAX:a[i]);
                
                int bj_1 = (j==0?INT_MIN:b[j-1]);
                int bj = (j==n?INT_MAX:b[j]);
                
                if(ai_1 <= bj){ 
                    lmax = max(ai_1,bj_1);
                    rmin = min(ai,bj);
                    l = i+1;    
                }else{ 
                    r = i-1;
                }
            }
        
            if( (m+n)%2==0){ 
                return (lmax+ rmin)/2.0;
            }else{ 
                return lmax;
            }
            return 0;
        }
    };

![在这里插入图片描述][2021030515245258.png]

[2021030515245258.png]: /images/20221023/07d1e7a52b004101af6f844a14af43c6.png