Leetcode4 寻找两个有序数组的中位数

题面描述 寻找两个有序数组的中位数，要求时间复杂度 $ O\left( \log_2 \left(n + m \right) \right)$

给定两个单调非减的有序数组，保证不全为空。求这两个数组合并后的中位数，要求时间复杂度 $ O\left( \log_2 \left(n + m \right) \right)$ 。

最朴素的想法肯定是二分套二分，考虑到第二个二分的size也会快速递减，时间复杂度应该在小常数 $ O \left( \log_2 n \cdot \log_2 m \right) $ 。

事实上这已经是非常优秀的复杂度了。如果面试官面我这个问题，我会说在普通电脑能储存存的数据规模下，上述复杂度和要求复杂度在计算时间上可能差异不大，在工程的考量上可以采用前者，因为前者实现更简洁不易产生bug。

正解没有想到，看了题解脑海里才冒出”k-th element”这个词（虽然不太贴切）。最近题目刷少了，思维码力都不行啊。

然后就是繁琐的实现过程，可能写得不是太好。

• 考虑到两个有序数组求第 $k$ 大，分别取数组第 $\frac{k}{2}$ 个元素
  • 如果第一个数组的第 $\frac{k}{2}$ 个元素比较小，那表示第一个数组的前 $\frac{k}{2}$ 个元素都太小。抛弃这个部分，继续求剩下数组第 $\frac{k}{2}$ 小。
  • 反之亦然
• 如果数组元素个数不够 $\frac{k}{2}$ 个，则比较最后一个值和另一个数组第 $\frac{k}{2}$ 个元素的大小
  • 如果最后一个值较小，那么直接从另一个数组里出答案
  • 否则，抛弃另一个数组前 $\frac{k}{2}$ 个元素，继续求剩下第 $\frac{k}{2}$ 小。

所谓抛弃一部分，只涉及指针位置的修改而非物理意义上的删除。那么每次问题规模折半，从分治角度出发这就是单分规模支折半问题，经典的对数复杂度。

考虑到初始 $ k= \frac{m+n}{2}$ 故总复杂度 $ O\left( \log_2 \left(n + m \right) \right)$ 。

另外还有各种细节：

• 一个数组为空的时候要避免访问该数组
• 给小规模问题一个出口总是好的（比如 $k=0$ 求第0小，那么一定是最小的两个数中小的那个）
• 偶数个数的中位数问题（如果偷懒可以二分两遍，但一定有更好的做法）

class Solution {

Comment: 最近Leetcode推出每日一题的活动，3月1日开始，我准备坚持参加一下