力扣-4-寻找两个正序数组的中位数

发布时间 2023-08-20 14:20:28作者: YaosGHC

题目要求O(log (m+n))的时间复杂度

知道了两个数组的长度,那么中位数的下标以及如何计算是可以确定的,给出的是两个正序数组,如果使用双指针,从两个数组头开始扫描并比较,找出合并后第 K 小的数字,时间复杂度是多少?

时间复杂度是O((M+N)/2),这个目标还不及题目的要求,看到logN就会想到二分,但是以往的二分是在有序数组中查找指定元素,这里是查找合并后的中位元素,或者说查找合并后第 K 小的元素,似乎不太一样

官方二分

这种思路的精髓在于:每一次循环都能排除掉当前比较中较小的那部分元素,从而在不断缩小的范围内寻找到中位数,而不需要对整个数组进行排序

这个二分思路中 k 的更新规则是什么,以及循环退出条件是什么?

k 的更新规则是每次循环结束后减去排除掉的元素数量,以更新我们在剩下的数组中查找新的第k小的元素

为什么这么做是正确的呢?

因为我们只会从数组头排除,也就是排除小的那一部分;结束条件是k=1,即我们需要第一小的元素,就是当前指针指向的两个元素。
但是很明显就算当k=1时,也有两个指针指向了两个数字,我们选哪一个呢?为什么选较小的那个作为中位数是正确的?
因为我们需要第一小的元素,就是更小的那一个

这个二分思路跟常规二分不一样的地方在于:首先它只会排除左边的部分,但是是两个数组中的某一个左半部分,用两个指针来实现。

我想这个思路可能更像是:查找合并数组后第 k 小的元素,更像是转化为 -> 排除掉合并后数组中最小的 k-1 个元素,并且每次排除 k/2 个元素,我觉得这样解释这个思路更能让人理解

如果能够理解这个思路了,那么就可以尝试自己写