Thursday, May 4, 2017

LeetCode 2nd time 4. Median of Two Sorted Arrays Leet code Java

 public double findMedianSortedArrays(int[] nums1, int[] nums2) {  
     int m=nums1.length;  
     int n=nums2.length;  
     if((m+n)%2==1){  
       return (double)findKHelper(nums1,nums2,0,m-1,0,n-1,(m+n+1)/2);  
     }  
     else {  
       return ((double)findKHelper(nums1,nums2,0,m-1,0,n-1,(m+n)/2)+(double)findKHelper(nums1,nums2,0,m-1,0,n-1,(m+n)/2+1))/2;  
     }  
   }  
   public int findKHelper(int[] nums1, int[] nums2, int l1, int r1, int l2, int r2,int k){  
     int m=r1-l1+1;  
     int n=r2-l2+1;  
     if(m>n) return findKHelper(nums2,nums1,l2,r2,l1,r1,k);  
     if(m==0) return nums2[l2+k-1];  
     if(k==1) return Math.min(nums1[l1],nums2[l2]);  
     int posA=Math.min(k/2,m);  
     int posB=k-posA;  
     if(nums1[l1+posA-1]==nums2[l2+posB-1]){  
       return nums1[l1+posA-1];  
     }  
     else if(nums1[l1+posA-1]<nums2[l2+posB-1]){  
       return findKHelper(nums1,nums2,l1+posA,r1,l2,l2+posB-1,k-posA);  
     }  
     else return findKHelper(nums1,nums2,l1,l1+posA-1,l2+posB,r2,k-posB);  
   }  

No comments:

Post a Comment