Leetcode and Lintcode

Median of Two Sorted Arrays

Problem:

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

Example
Given A=[1,2,3,4,5,6] and B=[2,3,4,5], the median is 3.5.

Given A=[1,2,3] and B=[4,5], the median is 3.

Challenge
The overall run time complexity should be O(log (m+n)).
Leetcode link
Lintcode link

My Solution:

This is a classic problem, which can be viewed as another form: “Given two sorted array, how to find the k-th largest number among both arrays?”.

The k in this problem is “total length / 2” for odd number. If the total length is even, we need to find “total length / 2” and “total length / 2 + 1” number, and then get the average value.

The most intuitive solution is to merge them and find the k-th number, which takes O(M + N);

There is a better solution. Assume both amount of elements in A and B are greater than k / 2. If we compare the (k / 2)-th value in A (A[k / 2 - 1]) and the (k / 2)-th value in B (B[k / 2 - 1]), we have three possilbe cases:

  • If A[k / 2 - 1] == B[k / 2 - 1], we can say the value is the k-th value we want.
  • If A[k / 2 - 1] < B[k / 2 - 1], it means integer from A[0] to A[k / 2 - 1] should be smaller than the k-th value, so we can drop these values.
  • If A[k / 2 - 1] > B[k / 2 - 1], it means integer from B[0] to B[k / 2 - 1] should be smaller than the k-th value, so we can drop these values.

To drop the values in A and B, we can use two pointers to point to the start index of A and B respectively.
We can build a recursion whose stop points are:

  • If the start index pointer of A or B exceed the length, return B[BStart + k - 1] or A[AStart + k - 1];
  • If k == 1, return the minimum of A[AStart] or B[BStart]
  • If A[AStart + k / 2 -1] == B[BStart + k / 2 -1], return the value.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/*************************************************************************
	> File Name: MedianOfTwoSortedArray.java
	> Author: Yao Zhang 
	> Mail: psyyz10@163.com 
	> Created Time: Tue 10 Nov 22:01:06 2015
 ************************************************************************/

public class MedianOfTwoSortedArray{
    public double findMedianSortedArrays(int[] A, int[] B) {
        int len = A.length + B.length;
        if (len % 2 != 0)
            return findKth(A,0,B,0,len / 2 + 1); 
        else
            return (findKth(A,0,B,0,len / 2) + findKth(A,0,B,0,len / 2 + 1)) / 2.0;
    }   
        
    public static int findKth(int[] A, int AStart,
                                int[] B, int BStart, int k){ 
        if (AStart >= A.length)  
            return B[BStart + k - 1] ;
        if (BStart >= B.length)  
            return A[AStart + k - 1] ;
        if (k == 1)
            return Math.min(A[AStart],B[BStart]);
        
        int va = AStart + k / 2 <= A.length ? 
            A[AStart + k / 2 -1] : Integer.MAX_VALUE;
        int vb = BStart + k / 2 <= B.length ? 
            B[BStart + k / 2 -1] : Integer.MAX_VALUE;
        
        if (va < vb) 
            return findKth(A, AStart + k / 2, B, BStart, k - k / 2);
        else if (va > vb) 
            return findKth(A, AStart, B, BStart + k / 2, k - k / 2);
        else 
            return va; 
    } 
}