求第k大

0Zero丶紫瞳 · 2018-09-27 06:29:36 · 个人记录

• 解法1：我们可以对这个乱序数组按照从大到小先行排序，然后取出前k大，总的时间复杂度为O(n*logn + k)。

• 解法2：利用选择排序或交互排序，K次选择后即可得到第k大的数。总的时间复杂度为O(n*k)

• 解法3：利用快速排序的思想，从数组S中随机找出一个元素X，把数组分为两部分Sa和Sb。Sa中的元素大于等于X，Sb中元素小于X。这时有两种情况：

  1. Sa中元素的个数小于k，则Sb中的第k-|Sa|个元素即为第k大数；
  2. Sa中元素的个数大于等于k，则返回Sa中的第k大数。时间复杂度近似为O(n)

• 解法4：二分[Smin,Smax]查找结果X，统计X在数组中出现，且整个数组中比X大的数目为k-1的数即为第k大数。时间复杂度平均情况为O(n*logn)

• 解法5：用O(4n)的方法对原数组建最大堆，然后pop出k次即可。时间复杂度为O(4n + k*logn)

• 解法6：维护一个k大小的最小堆，对于数组中的每一个元素判断与堆顶的大小，若堆顶较大，则不管，否则，弹出堆顶，将当前值插入到堆中。时间复杂度O(n * logk)

• 解法7：利用hash保存数组中元素Si出现的次数，利用计数排序的思想，线性从大到小扫描过程中，前面有k-1个数则为第k大数，平均情况下时间复杂度O(n)