第k大数（前k大数）

题目：设计一组N个数，确定其中第k个最大值

1,普通方法（先排序，然后遍历，得到第k大的数）注：如果是数组，直接arr[k]，我们可以对这个乱序数组按照从大到小先行排序，然后取出前k大，总的时间复杂度为O(n*logn + k)，即O(n*logn ）

2.利用部分排序，以避免N-K个数字的排序，例如用选择排序，或者冒泡排序，K次选择后即可得到第k大的数。总的时间复杂度为O(n*k)

此方法在k很小的时候，效率不错

3.利用堆排序：建立大顶堆，每次弹出最大值，然后调整堆，再次建立大顶堆，弹出次大值，，op出k次即可。时间复杂度为O(n + k*logn)，即O（k*logn)

建堆的时间复杂度是o（n），调整堆的时间复杂度是lgn，调用了n-1次，所以堆排序的时间复杂度是O(nlgn)

4,利用堆排序：建立小顶堆

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

6.利用quicksort思想，常见方法，时间复杂度为o（n）参考算法导论

我们可以借助quicksort的思想，把数组的值分成两部分，一部分比那个pivot大，一部分比pivot小，因为我们知道pivot在数组中的位置，所以比较k和pivot的位置就知道第k大的值在哪个范围，我们不断的进行recursion, 直到pivot就是第K大的值。时间复杂度，出乎意料，为O(N)，但是这是平均复杂度。为何它的平均复杂度比quicksort的复杂度低呢？重要原因是quicksort要对pivot两边的子数组还要排序，而我们其实只需要对其中一个进行处理，所以复杂度更低。具体怎么推导，请参考算法导论。

从数组S中随机找出一个元素X，把数组分为两部分Sa和Sb。Sa中的元素大于等于X，Sb中元素小于X。这时有两种情况：
1. Sa中元素的个数小于k，则Sb中的第k-|Sa|个元素即为第k大数；
2. Sa中元素的个数大于等于k，则返回Sa中的第k大数。时间复杂度近似为O(n)

7，计数排序（用hash实现），hash_map可实现排序

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

编程之美p145

巴特西

第k大数（前k大数）

最新文章

热门文章