怎么求数组中第K大的数
如何求数组中第K大的数？
对于任意给定的整型数组a[n]，设计一个算法求第K大的数。要求，其算法复杂度为O(n)。
请大家谈谈你们的思路。。。
------解决思路----------------------
2楼的方法肯定不是最好的。
解法：维护一个k大小的最小堆，对于数组中的每一个元素判断与堆顶的大小，若堆顶较大，则不管，否则，弹出堆顶，将当前值插入到堆中。时间复杂度O(n * logk)
解法：利用hash保存数组中元素Si出现的次数，利用计数排序的思想，线性从大到小扫描过程中，前面有k-1个数则为第k大数，平均情况下时间复杂度O(n)
------解决思路----------------------
用最小堆来做是比较好的方案。
------解决思路----------------------
LZ，解决这个问题的办法一般有两个：
1）先排序再查找：排序算法在O（n）的有三个：计数排序、桶排序、基数排序。其他就好办了。
2）经典的思想是：活用数据结构：建一个最小堆，建好之后选第k大的。
对于任意给定的整型数组a[n]，设计一个算法求第K大的数。要求，其算法复杂度为O(n)。
请大家谈谈你们的思路。。。
------解决思路----------------------
2楼的方法肯定不是最好的。
解法：维护一个k大小的最小堆，对于数组中的每一个元素判断与堆顶的大小，若堆顶较大，则不管，否则，弹出堆顶，将当前值插入到堆中。时间复杂度O(n * logk)
解法：利用hash保存数组中元素Si出现的次数，利用计数排序的思想，线性从大到小扫描过程中，前面有k-1个数则为第k大数，平均情况下时间复杂度O(n)
------解决思路----------------------
用最小堆来做是比较好的方案。
------解决思路----------------------
LZ，解决这个问题的办法一般有两个：
1）先排序再查找：排序算法在O（n）的有三个：计数排序、桶排序、基数排序。其他就好办了。
2）经典的思想是：活用数据结构：建一个最小堆，建好之后选第k大的。