> For the complete documentation index, see [llms.txt](https://mnunknown.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://mnunknown.gitbook.io/algorithm-notes/binary_search_lei/median_of_two_sorted_arrays.md).

# \*\*Median of Two Sorted Arrays

### [Median of Two Sorted Arrays](https://leetcode.com/problems/median-of-two-sorted-arrays/)

对于中位数问题，首先要做的是明白“找中位数” 等价于 find kth largest element，奇数元素找一遍，偶数元素找两遍。

所谓 “第 kth 的元素”，也叫 Order Statistic，在算法导论上有章节对这类问题有很详细的描述。

![](/files/-MUt7bd_LzDUNM37Q0O5)

#### 有向箭头"A -> B"代表 "A > B"，图中黑点为元素(quick-select 分组出来的，不是排序)，白点为分组中位数，阴影部分元素，都一定比 x 大。

#### 这个算法的核心思想是，每次可以扔掉 A 或 B 里面，较小的那 k / 2 个数，使得 A 与 B 的剩余搜索范围单调向右，而 k 指数缩小。

#### 复杂度 O(log k)，k = (m + n) / 2

```java
public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len = nums1.length + nums2.length;
        if(len % 2 == 1){
            return findKth(nums1, 0, nums2, 0, len / 2 + 1);
        } else {
            return (findKth(nums1, 0, nums2, 0, len / 2) + 
                    findKth(nums1, 0, nums2, 0, len / 2 + 1)) / 2.0;  
        }
    }

    private int findKth(int[] A, int startA, int[] B, int startB, int k){
        if(startA == A.length) return B[startB + k - 1];
        if(startB == B.length) return A[startA + k - 1];
        if(k == 1) return Math.min(A[startA], B[startB]);

        int keyA = (startA + k / 2 - 1 < A.length)
                    ? A[startA + k / 2 - 1]
                    : Integer.MAX_VALUE;
        int keyB = (startB + k / 2 - 1 < B.length)
                    ? B[startB + k / 2 - 1]
                    : Integer.MAX_VALUE;
        if(keyA < keyB){
            return findKth(A, startA + k / 2, B, startB, k - k / 2);
        } else {
            return findKth(A, startA, B, startB + k / 2, k - k / 2);
        }
    }
}
```

## (F) [Median of K sorted arrays](http://stackoverflow.com/questions/6182488/median-of-5-sorted-arrays)

![](/files/-MUt7bdaigsV68xrxqmJ)

<http://stackoverflow.com/questions/6182488/median-of-5-sorted-arrays>

其实这个博客里解 median of Two sorted array 的思路更适合解这个 k 的情况，因为这个做法更像图里的 order statistics:

<http://fisherlei.blogspot.com/2012/12/leetcode-median-of-two-sorted-arrays.html>

这题比较简单的使用 heap 的解法也可以用类似于[ Kth Smallest Element in a Sorted Matrix](https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/) 的 minHeap 做法；自定义一个 Tuple，存有 x, y 和 val 信息并根据 val 值 implement comparable interface，相当于在 m 个排序数组里面找 kth smallest number.

#### 时间复杂度：m 个数组，假如每个数组元素平均为 n，总共有 m\*n 个元素，中位数要找 mn/2 小的元素，heap size 最大为 m

#### 因此 O(mn \* log(m))


---

# 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://mnunknown.gitbook.io/algorithm-notes/binary_search_lei/median_of_two_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.