寻找第K大的数

小咪咪 2022-05-21 03:20 126阅读 0赞

1，对于一个有序数组

则为第K个数，O（1）

2，对于一个无序数组

使用修改的快排划分算法，时间复杂度为O（n）

3，对于两个无序数组

合并（不是真的合并，只是看出一个数组），则时间复杂度为O(n+m）

4，对于两个有序（假设递增）数组

[http://www.51nod.com/question/index.html\#!questionId=217][http_www.51nod.com_question_index.html_questionId_217]

在两个有序数组中进行二分搜索：时间复杂度为O（logn+logm）

先比较两个数组k/2的元素，如果相等，返回

否则较大的那个索引减去k/4，较小的那个索引加上k/4，继续比较。

这样不停二分下去，直至两边相等或索引达到了边界（0或k）。

5，对于一个行列都递增的二维矩阵n\*m，查找中位数

[http://zhiqiang.org/blog/science/computer-science/median-algorithm-of-ordered-matrix.html][http_zhiqiang.org_blog_science_computer-science_median-algorithm-of-ordered-matrix.html]

使用类似Tarjan的线性中位数的方法，每次找每列中位数，然后找中位数的中位数，

之后可以删除前一半列的上半部分或者后一半列的下半部分，这样可以实现复杂性 *O*(*n*log2*n*)

6，一种特殊的二维矩阵，查找第K大数

[http://www.51nod.com/question/index.html\#!questionId=46][http_www.51nod.com_question_index.html_questionId_46]

2个整数数组A,B，长度分别为m，n。从A，B中各选1个元素A\[i\],B\[j\]，相加后得到C\[i,j\]，

共有m\*n种选择方式，对应m\*n个数，求这m\*n个数中第K大的数是多少？

时间复杂度为：O（(m+n)\*log(Max-Min)）。

[http_www.51nod.com_question_index.html_questionId_217]: http://www.51nod.com/question/index.html#!questionId=217
[http_zhiqiang.org_blog_science_computer-science_median-algorithm-of-ordered-matrix.html]: http://zhiqiang.org/blog/science/computer-science/median-algorithm-of-ordered-matrix.html
[http_www.51nod.com_question_index.html_questionId_46]: http://www.51nod.com/question/index.html#!questionId=46