**Median of Two Sorted Arrays
对于中位数问题,首先要做的是明白“找中位数” 等价于 find kth largest element,奇数元素找一遍,偶数元素找两遍。
所谓 “第 kth 的元素”,也叫 Order Statistic,在算法导论上有章节对这类问题有很详细的描述。
有向箭头"A -> B"代表 "A > B",图中黑点为元素(quick-select 分组出来的,不是排序),白点为分组中位数,阴影部分元素,都一定比 x 大。
这个算法的核心思想是,每次可以扔掉 A 或 B 里面,较小的那 k / 2 个数,使得 A 与 B 的剩余搜索范围单调向右,而 k 指数缩小。
复杂度 O(log k),k = (m + n) / 2
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 的 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))
Last updated