Java O(log(m+n)) solution using find the Kth element technique


  • 0
    public class Solution {
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            int l1=nums1.length; int l2=nums2.length; int ltotal=l1+l2;
            if(ltotal%2!=0){
                return findKth(nums1, nums2, ltotal/2+1);
            }
            else{
                return (findKth(nums1, nums2, ltotal/2) + findKth(nums1, nums2, ltotal/2 +1))/2;
            }
        }
        public static double findKth(int[] nums1, int[] nums2, int k){
    		int l1=nums1.length; int l2 =nums2.length;
            if(l1==0 & l2>0){
                return nums2[k-1];
            }
            if(l1>0 & l2==0){
                return nums1[k-1];
            } 
            if(k==1){
                return Math.min(nums1[0], nums2[0]);
            }
            int i=Math.min(l1,k/2);
            int j=Math.min(l2,k/2);        
            if(nums1[i-1]>nums2[j-1]){
            	int temp1[]=new int[l2-j];
            	for(int p=0; p<temp1.length;p++){
            		temp1[p]=nums2[p+j];
            	}
                return findKth(nums1, temp1, k-j);
            }
            else{
            	int temp2[]= new int[l1-i];
            	for(int q=0;q<temp2.length;q++){
            		temp2[q]=nums1[q+i];
            	}
                return findKth(temp2, nums2, k-i);
            }        
        }
    }

Log in to reply
 

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