Iterative Solution C# O(lg(m+n))


  • 0
    S
    public class Solution {
    public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1 = nums1.Length;
        int len2 = nums2.Length;
        if((len1+len2)%2==1)return findKth(nums1,0,len1-1,nums2,0,len2-1,(len1+len2)/2+1);
        int first = findKth(nums1,0,len1-1,nums2,0,len2-1,(len1+len2)/2);
        int second = findKth(nums1,0,len1-1,nums2,0,len2-1,(len1+len2)/2+1);
        return (Convert.ToDouble(first)+Convert.ToDouble(second))/2;
    }
    
    public int findKth(int[] a, int la, int ra, int[] b, int lb, int rb, int k){
        
        if(ra<la)return b[lb+k-1];
        if(rb<lb)return a[la+k-1];
        while(la<=ra&&lb<=rb){
            int ma=la+(ra-la)/2;
            int mb=lb+(rb-lb)/2;
            if(a[ma]<=b[mb]){
                if(k<=(ma-la+1+mb-lb)){
                    rb=mb-1;continue;
                }else{
                    k-=(ma-la+1);la=ma+1;
                }
            }else{
                if(k<=(ma-la+1+mb-lb)){
                    ra=ma-1;continue;
                }else{
                    k-=(mb-lb+1);lb=mb+1;
                }
            }
        }
        return la>ra?b[lb+k-1]:a[la+k-1];
    }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.