> For the complete documentation index, see [llms.txt](https://loghead.gitbook.io/algorithm-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://loghead.gitbook.io/algorithm-notes/array-matrix-interval-binary-indexed-tree/median-of-k-sorted-arrays.md).

# Median of K Sorted Arrays

LintCode 931

> There are `k`sorted arrays `nums`. Find the median of the given `k`sorted arrays.
>
> ## 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.
>
> **Example**
>
> Given nums =`[[1],[2],[3]]`, return `2.00`.

这题难度起始比上一题 median of two sorted arrays 要简单，因为不需要找到 O(logN) 之类的解 （网上没找到）

第一个思路当然就是 heap 了。时间复杂度是 O(M logK)。M是所有数组总长度，如果每个数组平均长度是 N，那么时间复杂度是 O(NK log K)。这个解法能出争取结果，不过在 88% 的时候碰到一个很长的 test case TLE 了

```python
    def findMedian(self, nums):
        import heapq
        length = 0
        minheap = []
        for i, array in enumerate(nums):
            if array:
                heapq.heappush(minheap, (array[0], i, 0))
                length += len(array)

        if length == 0:
            return 0.0

        idx1, idx2 = (length - 1) // 2, length // 2

        count = 0
        while minheap:
            n, i, j = heapq.heappop(minheap)
            if count == idx1:
                median1 = n
            if count == idx2:
                median2 = n
                break
            if j + 1 < len(nums[i]):
                heapq.heappush(minheap, (nums[i][j + 1], i, j + 1))
            count += 1

        return (median1 + median2) / 2.0
```

第二个思路就是对数值二分。反正这种很搞的方法竟然还挺快。python 勉强能过。我看九章给的java答案，直接可以从 `[0, sys.maxint]` 开始二分。如果python code 这样写，在 77% 左右会 TLE。所以下面先算了下最大值。

这个时间复杂度是 O(log(range)\*log(N)\*K)。因为range是 0 \~ 2^31 - 1 （正整数取值范围），所以log(range)最多是31

LintCode上，python code的连这个常数项也要优化下才能AC

```python
import bisect

class Solution:
    """
    @param nums: the given k sorted arrays
    @return: the median of the given k sorted arrays
    """
    def findMedian(self, nums):
        # write your code here
        length, self.maxValue = 0, 0
        for array in nums:
            if array:
                length += len(array)
                self.maxValue = max(self.maxValue, array[-1])

        if length == 0:
            return 0.0

        if length % 2 == 1:
            return self.findKth(nums, length // 2 + 1) * 1.0

        return (self.findKth(nums, length // 2) + self.findKth(nums, length // 2 + 1)) / 2.0


    def findKth(self, nums, k):
        lo, hi = 0, self.maxValue
        while lo < hi:
            mid = (lo + hi) // 2
            n = self.findLessEqual(nums, mid)
            if n < k:
                lo = mid + 1
            else:
                hi = mid
        return lo


    def findLessEqual(self, nums, value):
        count = 0
        for array in nums:
            count += bisect.bisect(array, value)
        return count
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://loghead.gitbook.io/algorithm-notes/array-matrix-interval-binary-indexed-tree/median-of-k-sorted-arrays.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.