Buttercola: Leetcode: Median of Two Sorted Arrays

There are two sorted arrays A and B 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)).

Understand the problem:
The problem gives two sorted array, A and B. Find out the median of the two sorted arrays.
Note that the time complexity is required to be O(log(m+n)).

An initial thought was firstly merge the two arrays, then median is the number on A.length + B.length - 1 / 2. However, merging will take O(m + n) time, which however the algorithm asks for a solution in log time. So it is naturally to think about the binary search.

One thing must take note is the definition of the median of a sorted array. Note that the return number is double in the problem. So if the array length is even, e.g. 1, 2, 3, 4. The median is the average of 2 and 3, i.e., 2 + 3 / 2 = 2.5

Solution:
http://fisherlei.blogspot.com/2012/12/leetcode-median-of-two-sorted-arrays.html
http://www.lifeincode.net/programming/leetcode-median-of-two-sorted-arrays-java/

The problem is equivalent to find the kth element in the two sorted array. The key is to decide how to eliminate part of the array each recursion.

Code (Java):

public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1 == null || nums2 == null) {
            return 0.f;
        }
         
        int n1 = nums1.length;
        int n2 = nums2.length;
         
        if ((n1 + n2) % 2 == 1) {
            return findMedianHelper(nums1, nums2, (n1 + n2) / 2 + 1);
        } else {
            return (findMedianHelper(nums1, nums2, (n1 + n2) / 2) + 
                    findMedianHelper(nums1, nums2, (n1 + n2) / 2 + 1)) / 2;
        }
    }
     
    private double findMedianHelper(int[] nums1, int[] nums2, int k) {
        if (nums1 == null || nums1.length == 0) {
            return nums2[k - 1];
        }
         
        if (nums2 == null || nums2.length == 0) {
            return nums1[k - 1];
        }
         
        if (k == 1) {
            return Math.min(nums1[0], nums2[0]);
        }
         
        int n1 = nums1.length;
        int n2 = nums2.length;
         
        if (nums1[n1 / 2] > nums2[n2 / 2]) {
            if ((n1 / 2 + n2 / 2 + 1) >= k) {
                return findMedianHelper(Arrays.copyOfRange(nums1, 0, n1 / 2), nums2, k);
            } else {
                return findMedianHelper(nums1, Arrays.copyOfRange(nums2, n2 / 2 + 1, n2), 
                                        k - (n2 / 2 + 1));
            }
        } else {
            if ((n1 / 2 + n2 / 2 + 1) >= k) {
                return findMedianHelper(nums1, Arrays.copyOfRange(nums2, 0, n2 / 2), k);
            } else {
                return findMedianHelper(Arrays.copyOfRange(nums1, n1 / 2 + 1, n1), 
                                        nums2, k - (n1 / 2 + 1));
            }
        }
    }
}<b>
<span style="font-family: "arial" , "helvetica" , sans-serif;">Edit on 4/27/20:</span></b>

public class Solution {
    /*
     * @param A: An integer array
     * @param B: An integer array
     * @return: a double whose format is *.5 or *.0
     */
    public double findMedianSortedArrays(int[] A, int[] B) {
        // write your code here
        int n = A.length + B.length;
         
        if (n % 2 == 1) {
            return findMedianSortedArraysHelper(A, 0, B, 0, n / 2 + 1);
        } else {
            return ((double) findMedianSortedArraysHelper(A, 0, B, 0, n / 2) + 
                findMedianSortedArraysHelper(A, 0, B, 0, n / 2 + 1)) / 2;
        }
    }
     
    private int findMedianSortedArraysHelper(int[] A, int startOfA, int[] B, int startOfB, int k) {
        if (startOfA >= A.length) {
            return B[startOfB + k - 1];
        }
         
        if (startOfB >= B.length) {
            return A[startOfA + k - 1];
        }
         
        if (k == 1) {
            return Math.min(A[startOfA], B[startOfB]);
        }
         
        int halfOfA = startOfA + k / 2 - 1 >= A.length ? 
            Integer.MAX_VALUE : A[startOfA + k / 2 - 1];
        int halfOfB = startOfB + k / 2 - 1 >= B.length ?
            Integer.MAX_VALUE : B[startOfB + k / 2 - 1];
             
        if (halfOfA < halfOfB) {
            return findMedianSortedArraysHelper(A, startOfA + k / 2, B, startOfB, k - k / 2);
        } else {
            return findMedianSortedArraysHelper(A, startOfA, B, startOfB + k / 2, k - k / 2);
        }
    }
}

The complexity is log(k), where k is the kth elements after merged of the two arrays. For this particular problem, the k = (n + m) / 2.

So why the complexity is logk? It's because for each time we can eliminate k/2 data in O(1) time. So overall the complexity is logk.

Buttercola

Thursday, September 25, 2014

Leetcode: Median of Two Sorted Arrays

No comments:

Post a Comment