@@ -31,11 +31,11 @@ The median is (2 + 3)/2 = 2.5
31
31
32
32
题意是给你两个已排序的递增数组,让你找出其中位数。
33
33
34
- 乍一看这题并不是很难,因为两序列有序,所以我们很容想到时间复杂度为` O(m + n) ` 的做法, 但这题要求的时间复杂度为` O(log(m + n)) ` ,那么我们自然而然地就能想到二分查找法 。
34
+ 乍一看这题并不是很难,因为两序列有序,所以我们很容想到时间复杂度为` O(m + n) ` 的做法:依次取出两数组中较小的元素,然后找到中间的元素即可。 但这题要求的时间复杂度为` O(log(m + n)) ` ,那么我们自然而然地就能想到二分查找法进行求解 。
35
35
36
36
题目是让找两数组的中位数,我们可以泛化为求两数组中第` k ` 大的元素,那么,求中位数就是其中的一个特例而已。` helper ` 函数所起到的作用就是求两数组中第` k ` 大的元素,下面来解释其原理:
37
37
38
- 假设数组分别记为` A ` ,` B ` ,当前需要搜索第` k ` 大的数,于是我们可以考虑从数组` A ` 中取出前` m ` 个元素,从数组` B ` 中取出 ` k - m ` 个元素。由于数组` A ` ,` B ` 分别排序,则` A[m - 1] ` 大于从数组` A ` 中取出的其他所有元素,` B[k - m - 1] ` 大于数组` B ` 中取出的其他所有元素。此时,尽管取出元素之间的相对大小关系不确定,但` A[m - 1] ` 与` B[k - m - 1] ` 的较大者一定是这` k ` 个元素中最大的。那么,较小的那个元素一定不是第` k ` 大的,这里留给读者自己想象。
38
+ 假设数组分别记为` A ` ,` B ` ,当前需要搜索第` k ` 大的数,于是我们可以考虑从数组` A ` 中取出前` m ` 个元素,从数组` B ` 中取出前 ` k - m ` 个元素。由于数组` A ` ,` B ` 分别排序,则` A[m - 1] ` 大于从数组` A ` 中取出的其他所有元素,` B[k - m - 1] ` 大于数组` B ` 中取出的其他所有元素。此时,尽管取出元素之间的相对大小关系不确定,但` A[m - 1] ` 与` B[k - m - 1] ` 的较大者一定是这` k ` 个元素中最大的。那么,较小的那个元素一定不是第` k ` 大的,这里留给读者自己想象。
39
39
40
40
为叙述方便,假设` A[m - 1] ` 是较小的那个元素,那么我们可以把` A[0] ` ,` A[1] ` ...` A[m - 1] ` 排除掉,并且更新` k ` 值为` k - m ` ,也就是下一次就是从剩余的元素中寻找第` k - m ` 大的元素,这样,我们就完成了一次范围缩小,同理进行下一轮的操作。
41
41