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)).

解法1: merge sort (O(m+n))

Analysis

• Merge two arrays to a new array (merge sort)
• Find the median for odd and even case

Code

public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if ((nums1==null || nums1.length==0) && (nums2==null || nums2.length==0)) return -1.0;

        int len1 = (nums1==null) ? 0 : nums1.length;
        int len2 = (nums2==null) ? 0 : nums2.length;
        int len = len1+len2;

        int[] merge = new int[len];
        int index1=0, index2=0, index3=0;

        while (index1<len1 && index2<len2){
            if (nums1[index1]<nums2[index2]) {merge[index3++]=nums1[index1++];}
            else {merge[index3++]=nums2[index2++];}
        }

        if (index1==len1){
            while (index2<len2) {merge[index3++]=nums2[index2++];}
        }
        else {
            while (index1<len1) {merge[index3++]=nums1[index1++];}
        }

        if (len%2==0){return (merge[len/2]+merge[len/2-1])/2.0;}
        else {return merge[len/2];}
    }
}

Note

• 注意最后return的时候除以2.0才能return double，如果写成2的话只return int

解法2: binary search (Olog(m+n))

• find kth number:
  • 如果nums1[k/2] < nums2[k/2]，合并后的前k的数一定包括nums1的多于前k/2个数和nums2的少于前k/2个数，说明nums1的前k/2个数一定在合并后的前k个数里。那么相当于从nums1的k/2开始，nums2的0开始合并，找第k-k/2个数。
  • 同理nums1[k/2]>nums2[k/2]的情况
  • 如果nums1的长度小于k/2，那么nums2的前k/2个数必须在合并后的前k个数里，放弃nums2的前k/2个数
  • 同理对于nums2的长度小于k/2的情况

Code

public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len = nums1.length + nums2.length;
        if (len%2==0){
            return (findKth(nums1, 0, nums2, 0, len/2)+findKth(nums1, 0, nums2, 0, len/2+1))/2.0;
        }
        else {
            return findKth(nums1, 0, nums2, 0, len/2+1);
        }
    }

    //find kth number of two sorted array
    private int findKth(int[] nums1, int index1, int[] nums2, int index2, int k){
        if (index1 >= nums1.length) return nums2[index2+k-1]; 
        if (index2 >= nums2.length) return nums1[index1+k-1];
        if (k==1) return Math.min(nums1[index1], nums2[index2]);

        int key1 = index1+k/2-1 >= nums1.length ?  Integer.MAX_VALUE : nums1[index1+k/2-1];
        int key2 = index2+k/2-1 >= nums2.length ?  Integer.MAX_VALUE : nums2[index2+k/2-1];

        if (key1 < key2){
            return findKth(nums1, index1+k/2, nums2, index2, k-k/2);
        }
        else {
            return findKth(nums1, index1, nums2, index2+k/2, k-k/2);
        }
    }
}

Reference

• Yuanbin
• 九章算法课video (course 2)