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);
}
Let's snipe the Leetcode problems together. No more hiding! Leetcode solution in Java! Your comments and suggestions are welcome!
Thursday, May 4, 2017
LeetCode 2nd time 4. Median of Two Sorted Arrays Leet code Java
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment