求第k大元素

问题描述

在数组中找到第k大的元素

样例

给出数组 [9,3,2,4,8],第三大的元素是 4

给出数组 [1,2,3,4,5],第一大的元素是 5,第二大的元素是 4,第三大的元素是 3,以此类推

解析

利用分治原理,我们来求解 

1 、取数组中的任意位置的元素,比如第一个元素作为参考值

2、遍历数组中的元素,比参考值大的放到一组, 小的放到一组,这里我们把等于参考值的也放到大值组。

3、k的值如果比大值组的长度还大就在小值组, 小就在大值组, 如果等于大值组的长度那么参考值就是我们要找的k大元素

4、3步骤得到的数组重复以上步骤(递归操作),直到3步骤得到我们需要的值

 



发表评论

电子邮件地址不会被公开。