Find Median
祸从天降的一天。 早上起不来,于是刷手机清醒一下,突然看到一个 ACMer 楼主提到自己没有刷过 Leetcode,面试的时候差点儿被打脸了。 看了一下题目,要求是 O(logn) 的复杂度,默默想了想,没有特别清晰的思路。 结果翻了翻评论,很多人都在蜻蜓点水般地表示二分查找不断分割就可以了。 要那么简单还用你说吗?起床了起床了。 题目是这样的: 给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。 我本来的想法是归并之后计算中位数,但只能做到 O(m+n),再优化感觉只能二分了。 于是又开始想分别取两个数组的中位数,比较之后就可以各扔掉一半,然后对两个折半的数组继续取中位数比较。 比如一开始找到的中位数是这样:[…5…], […10…],那么 5 的左边和 10 的右边就可以丢掉了,因为最终的中位数肯定在 5 和 10 中间。 如果接下来是这样:[5..8…], […7..10],那么 8 的右边和 7 的左边也可以丢掉,因为比 8 大的元素数量达不到这两个小数组的一半,所以中位数不会在里面,比 7 小的同理。 一直重复这个流程,最后得到的肯定就是一个或两个数,平均下就好了,时间复杂度也是符合要求的 O(logn). 结果等到看完标答后我才反应过来自己错在哪里了,这是后话。(因为 m 和 n 不一定一样大,所以显然折半的逻辑不对) 最优的解决方案是可以做到 O(log min(m, n)) 的,核心也是二分法,不过思路要复杂一些: 首先明确中位数的定义。对于奇数个数字来说是最中间的元素,偶数则是中间两个元素的平均值。 要做的是将两个数组各分一刀,假设划分的下标分别是 i 和 j,那么 nums1 被分成 nums1[0, i], nums1[i:],而 nums2 分为 nums2[0, j], nums2[j:]....