Movatterモバイル変換


[0]ホーム

URL:


Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

Sign up
Appearance settings

Commit4ee26f8

Browse files
committed
update: update 004
1 parent21ea0de commit4ee26f8

File tree

1 file changed

+2
-2
lines changed

1 file changed

+2
-2
lines changed

‎note/004/README.md

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -31,11 +31,11 @@ The median is (2 + 3)/2 = 2.5
3131

3232
题意是给你两个已排序的递增数组,让你找出其中位数。
3333

34-
乍一看这题并不是很难,因为两序列有序,所以我们很容想到时间复杂度为`O(m + n)` 的做法但这题要求的时间复杂度为`O(log(m + n))`那么我们自然而然地就能想到二分查找法
34+
乍一看这题并不是很难,因为两序列有序,所以我们很容想到时间复杂度为`O(m + n)` 的做法:依次取出两数组中较小的元素,然后找到中间的元素即可。但这题要求的时间复杂度为`O(log(m + n))`那么我们自然而然地就能想到二分查找法进行求解
3535

3636
题目是让找两数组的中位数,我们可以泛化为求两数组中第`k` 大的元素,那么,求中位数就是其中的一个特例而已。`helper` 函数所起到的作用就是求两数组中第`k` 大的元素,下面来解释其原理:
3737

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` 大的,这里留给读者自己想象。
3939

4040
为叙述方便,假设`A[m - 1]` 是较小的那个元素,那么我们可以把`A[0]``A[1]`...`A[m - 1]` 排除掉,并且更新`k` 值为`k - m`,也就是下一次就是从剩余的元素中寻找第`k - m` 大的元素,这样,我们就完成了一次范围缩小,同理进行下一轮的操作。
4141

0 commit comments

Comments
 (0)

[8]ページ先頭

©2009-2025 Movatter.jp