Median of two Sorted Arrays

• Lintcode : 65 / Leetcode : 4
• Level : Hard

Problem

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays.

Example
Example 1

Input:
A = [1,2,3,4,5,6]
B = [2,3,4,5]
Output: 3.5
Example 2

Input:
A = [1,2,3]
B = [4,5]
Output: 3
Challenge
The overall run time complexity should be O(log (m+n)).

Clarification
The definition of the median:

The median here is equivalent to the median in the mathematical definition.

The median is the middle of the sorted array.

If there are n numbers in the array and n is an odd number, the median is A[(n-1)/2]A[(n−1)/2].

If there are n numbers in the array and n is even, the median is (A[n / 2] + A[n / 2 + 1]) / 2.

For example, the median of the array A=[1,2,3] is 2, and the median of the array A=[1,19] is 10.

Concept & Algorithm

筆記

Time Complexity & Space Complexity

time : O(log(A.size() + B.size())
space: O(1)

Answer

class Solution {
public:
    double findMedianSortedArrays(vector<int> &A, vector<int> &B) {
        int len = A.size() + B.size();
        if (len == 0) return 0;
        double ret = 0;
        if (len & 1) {
            ret = finKth(A, B, 0, 0, len / 2 + 1);
        }else {
            ret = (finKth(A, B, 0, 0, len / 2) + finKth(A, B, 0, 0, len / 2 + 1)) / 2.0;
        }
        return ret;
    }
    int finKth (vector<int> &A, vector<int> &B, int a, int b, int k) {
        if (a >= A.size()) return B[b + k - 1];
        if (b >= B.size()) return A[a + k - 1];
        if (k == 1) return min(A[a], B[b]);
        int keyA = a + k / 2 - 1 >= A.size() ? INT_MAX : A[a + k / 2 - 1];
        int keyB = b + k / 2 - 1 >= B.size() ? INT_MAX : B[b + k / 2 - 1];
        if (keyA < keyB) {
            return finKth(A, B, a + k / 2, b, k - k / 2);
        }else {
            return finKth(A, B, a, b + k / 2, k - k / 2);
        }
    }
};

tags: other

​