m + n 为偶数时,中位数是位置为 (m + n)/2 和 (m + n)/2 + 1 的两个数的平均数
这个位置实际上表明了有多少个元素比中位数小。利用这一点,我们不用合并数组,只需要在两个数组中找出第 k 小的元素即可,其中 k = (m+n)/2 或 k = (m+n)/2 + 1。(如果 m + n是奇数,就只用找 k = (m+n)/2 的情况,如果是偶数,则两个都要找,然后求平均)
所以只要实现在两个数组中找到第 k 小的元素,这道题就可以解决了。
每次检查 A B 两个数组的 k/2 - 1 这个位置。如果 A[k/2 -1] < B[k/2 - 1],则因为数组有序,比 A[k/2 - 1] 这个数还小的数最多只有 A 中它前面的 k/2 - 1 个数以及 B 前面的最多 k/2 - 1 个数,最多也只有 k-2 个数比它小,那它肯定不是中位数,这个数以及它前面的全部排除。
假设这一步排除掉了 x 个数,且在数组中把这些数删掉。则新的问题变为在剩下的数组中寻找第 k - x 小的数了,是一模一样的子问题。更新 k 值,然后利用上面的逻辑一直迭代下去,直到最后 k == 1,就只用比较两个剩余数组最小的元素哪个更小就好了。有可能会出现将其中一个数组全部排除的情况,此时直接返回另一个数组第 k 个数即可。需要注意 k 的更新必须减去实际上排除掉的数字数目。