4. Median of Two Sorted Arrays(#1).java

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1 == null && nums2 == null) return 0.0;
        int len1 = nums1.length, len2 = nums2.length;
        int left = (len1 + len2) / 2;
        int right = (len1 + len2) / 2 + 1;
        if ((len1 + len2) % 2 != 0) {
            return (double)findKth(nums1, 0, nums2, 0, right);
        } else {
            return (findKth(nums1, 0, nums2, 0, left) + findKth(nums1, 0, nums2, 0, right)) / 2.0; 
        }
    }
    
    public int findKth(int[] nums1, int idx1, int[] nums2, int idx2, int k) {
        if (idx1 == nums1.length) return nums2[idx2 + k - 1];
        if (idx2 == nums2.length) return nums1[idx1 + k - 1];
        if (k == 1) return Math.min(nums1[idx1], nums2[idx2]);
        
        int mid1 = idx1 + k / 2 - 1;
        mid1 = mid1 >= nums1.length ? nums1.length - 1 : mid1;
        int mid2 = idx2 + k / 2 - 1;
        mid2 = mid2 >= nums2.length ? nums2.length - 1 : mid2;
        if (nums1[mid1] < nums2[mid2]) {
            return findKth(nums1, mid1 + 1, nums2, idx2, k - (mid1 - idx1 + 1));
        } else {
            return findKth(nums1, idx1, nums2, mid2 + 1, k - (mid2 - idx2 + 1));
        }
        
    }
}

4. Median of Two Sorted Arrays.java

/*
 * 1. brute force (m+n)log(m+n)
 * 2. Merge sort O(m+n)
 * 3. Comparing Medians log(m+n)
 * 4. Median Finding log(m+n) : check an element is median or not in constant time
 *    i 是A的中位数
      j = (m + n) / 2;
      case 1# : B[j] <= A[i] <= B[j + 1]
      case 2# : A[i] <= B[j] <= B[j + 1]
      case 3# : [j] <= B[j + 1] <=  A[i]
 */



public class Solution {
      
      // O(n)
    	public double findMedianSortedArraysV1(int[]nums1, int[]nums2) {
		int i = 0;
		int j = 0;
		int k = 0;
		int[]union = new int[nums1.length + nums2.length];
		while (i < nums1.length && j < nums2.length && k<=union.length/2) {
			if (nums1[i] < nums2[j]) {
				union[k++]=nums1[i++];
			} else {
				union[k++]=nums2[j++];
			}
		}
		while(i<nums1.length && k<=union.length/2){
			union[k++]=nums1[i++];
		}
		while(j<nums2.length && k<=union.length/2){
			union[k++]=nums2[j++];
		}
		if(union.length%2==1)
			return union[union.length/2];
		else
			return (union[union.length/2-1]+union[union.length/2])/2.0;
    }
    // O(log(m + n))
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        
        int nums1Len = nums1.length;
        int nums2Len = nums2.length;
        
        int len = nums1Len + nums2Len;
        if (len % 2 != 0){
            return findKth(nums1, 0, nums2, 0, len / 2 + 1 );
        } else {
            return ( findKth(nums1, 0, nums2, 0, len / 2) + findKth(nums1, 0, nums2, 0, len / 2 + 1) ) / 2.0;
        }
    }
    
    
    public int findKth( int[] nums1, int start1, int[] nums2, int start2, int k){// K begins with 1
        
        
        if (start1 >= nums1.length ){
            return nums2[start2 + k - 1];
        } 
        if (start2 >= nums2.length ){
            return nums1[start1 + k - 1];
        }
        
        if (k == 1){
            return Math.min(nums1[start1], nums2[start2]);
        }

        
        int median1 = (start1 + k/2 - 1) < nums1.length ? nums1[start1 + k/2 - 1] : Integer.MAX_VALUE;
        int median2 = (start2 + k/2 - 1) < nums2.length ? nums2[start2 + k/2 - 1] : Integer.MAX_VALUE;
        
        if (median1 < median2){
        	return findKth( nums1, start1 + k/2 , nums2, start2, k - k/2);
        } else {
        	return findKth( nums1, start1, nums2, start2 + k/2, k - k/2);
        }
        
    }
    
}