Median of K Sorted Arrays

• Lintcode : 931
• Level : Hard

Problem

There are k sorted arrays nums. Find the median of the given k sorted arrays.

Example
Example 1:

Input:
[[1],[2],[3]]
Output:
2.00
Example 2:

Input:
[[1,1,2],[2,4,8],[3,7,10,20]]
Output:
3.50
Notice
The length of the given arrays may not equal to each other.
The elements of the given arrays are all positive number.
Return 0 if there are no elements in the array.
In order to ensure time complexity, the program will be executed repeatedly.

Concept & Algorithm

筆記

Time Complexity & Space Complexity

time : O(log(maximum - minimum) n logm)
(n = elements in nums, m = avg elements in n)
space: O(1)

Answer

class Solution {
public:
    double findMedian(vector<vector<int>> &nums) {
        if (nums.size() == 0) return 0;
        int n = 0;
        for (auto i : nums) {
            if (i.empty()) continue;
            n += i.size();
        }
        if (n == 0) return 0;
        if (n & 1) {   
            return findKth(nums, n / 2 + 1);    
        }else {
            return (findKth(nums, n / 2) + findKth(nums, n / 2 + 1)) / 2.0;
        }
    }

private:
    double findKth (vector<vector<int>> &nums, int k) {
        int lb = INT_MAX, ub = INT_MIN;
        for (auto i : nums){
            if (i.empty()) continue;
            lb = min(lb, i[0]);
            ub = max(ub, i.back());
        }
        int start = lb, end = ub;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (count(nums, mid) >= k) {
                end = mid;
            }else if (count(nums, mid) < k) {
                start = mid; ;
            }
        }
        if (count(nums, start) == k) return start;
        return end;
    }
    int count(vector<vector<int>> &nums, int key) {
        int count = 0;
        for (auto i : nums) {
            if (i.empty()) continue;
            count += countLessAndEqual(i, key);
        }
        return count;
    }
    int countLessAndEqual(vector<int> &n, int key) {
        int l = 0, r = n.size() - 1; 
        while (l + 1 < r) {
            int mid = l + (r - l) / 2;
            if (n[mid] <= key) {
                l = mid;
            }else {
                r = mid;
            }
        }
        if (n[l] > key) return l;
        if (n[r] > key) return r;
        return n.size();
    }
};

tags: Binary Search

​