求数组中第K个最大的值

Question

如题所述

Answer 1

那么有没有更好的方案？我们可以考虑从k入手。如果我们每次能够删除一个一定处于第k大元素之前的元素，那么需要进行k次。但是如果我们每次都能删除一半呢？可以利用A，B有序的信息，类似二分查找，也是充分利用有序。
假设A
和B
的元素个数都大于k/2，我们将A
的第k/2
个元素（即A[k/2-1]）和B
的第k/2个元素（即B[k/2-1]）进行比较，有以下三种情况（为了简化这里先假设k
为偶数，所得到的结论对于k
是奇数也是成立的）：
-
A[k/2
-
1]
==
B[k/2
-
1];
-
A[k/2
-
1]
>
B[k/2
-
1];
-
A[k/2
-
1]
<
B[k/2
-
1];
如果A[k/2
-
1]
<
B[k/2
-
1]
，意味着
A[0]
到
A[k/2
-
1]
的元素一定小于
A+B
第k大的元素。因此可以放心的删除A数组中的这k/2个元素；
同理，A[k/2
-
1]
>
B[k/2
-
1];可以删除B数组中的k/2个元素；
当A[k/2
-
1]
==
B[k/2
-
1]
时，说明找到了第k大的元素，直接返回A[k/2
-
1]
或B[k/2
-
1]的值。
因此可以写一个递归实现，递归终止条件是什么呢？
-
A或B为空时，直接返回A[k-1]
或
B[k-1]
-
当k
=
1时，返回min(A[0],
B[0])
//第1小表示第一个元素
-
当A[k/2
-
1]
==
B[k/2
-
1]
时，返回A[k/2
-
1]
或B[k/2
-
1]