2015年9月15日星期二

Leetcode 4 Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Solution 1: Best way is using binary search. If we want to find the kth element in final combined array. Let us say i elements in left part nums1 and j elements in left part of nums2. These left i+j=k element are less than the right part of nums1 and nums2 in final position. If violet, we can determine to search left half or right half. Complexity will be O(m), we can also swap nums1/2 to let m is small than n.
    The difficult part is to keep in bound. We use get(nums, index) function instead of nums[index] directly. If index out of lower bound, return Integer.MIN_VALUE; and when out of higher bound, return Integer.MAX_VALUE. Then we do not need to deal with all the corner cases. Make the code clean.

 public class Solution {  
   public double findMedianSortedArrays(int[] nums1, int[] nums2) {  
     int m=nums1.length;  
     int n=nums2.length;  
     int k=(m+n)/2;  
     int lo=0, hi=Math.min(m,k); //high is the min of m or k  
     while (lo<hi) {  
       int mid=lo+(hi-lo)/2;  
       int j=k-mid;  
       if (get(nums1,mid)>=get(nums2,j-1)) {  
         if (get(nums2,j)>=get(nums1,mid-1)) {  
           lo=mid;  
           hi=mid;  
         }  
         else hi=mid-1;  
       }  
       else lo=mid+1;  
     }  
     if ((m+n)%2==1) return Math.min(get(nums1,lo),get(nums2,k-lo));  
     //even, remeber to convert to double, otherwise xxxx.5 will be xxxx  
     return (double)(0.5*(Math.min(get(nums1,lo),get(nums2,k-lo))+Math.max(get(nums1,lo-1),get(nums2,k-lo-1))));  
   }  
   private int get(int[] nums, int index) {  
     int n=nums.length;  
     if (index<0) return Integer.MIN_VALUE;  
     if (index>=n) return Integer.MAX_VALUE;  
     return nums[index];  
   }  
 }  

没有评论:

发表评论