K大的数 _位数_甘肃龙网

问题：
从一个数组里面，找出第K大的数。
题目很简单，要想把第K个数找出来，其实也挺容易的。
第一种方法：无非就是先排序，比如用Merge Sort算法，整个算法复杂度为 O(NlgN), 然后找到第K个即可。
第二种方法：如果k很小，比如第五个最大的数，而整个数组的长度非常的大，那么，还有一种方法就是，我做k遍找最大的数，每做一遍，就把最大的放在数组的最后面，然后减少数组扫描的范围，就可以把第k大的数找出来，这样做的复杂度就是O(K*N)，在K很小的情况下，还是不错的。
第三种方法：我们可以借助的思想，把数组的值分成两部分，一部分比那个pivot大，一部分比pivot小，因为我们知道pivot在数组中的位置，所以比较k和pivot的位置就知道第k大的值在哪个范围，我们不断的进行, 直到pivot就是第K大的值。时间复杂度，出乎意料，为O(N)，但是这是平均复杂度。为何它的平均复杂度比的复杂度低呢？重要原因是要对pivot两边的子数组还要排序，而我们其实只需要对其中一个进行处理，所以复杂度更低。具体怎么推导，请参考算法导论。
但是本文讲的是另一个算法，叫做算法，它能在时间复杂度为O(N)的情况下找出第K大的数。先把算法贴出来，然后再讲。

文章插图
第一步：把数组分成\ n/5 \rfool 这么多子数组，每个子数组里包含5个数，因为会有无法整出的可能，所以最后一个子数组会小于5.
第二步：用把这5个数排序，然后找出中位数，也就是第3个。
【K大的数】第三步：把获得的中位数又排序，找出中位数的中位数。如果中位数的个数是偶数，那么取排好序的第 m/2 个数，m指的是中位数的个数。
第四步：然后呢，把原来的数组分成两个部分，一部分比那个“中位数的中位数”大，一部分比那个“中位数的中位数”小。我们可以假设左边的数大，右边的数小。然后我们可以得到“中位数的中位数”的位置i.
第五步：如果i =k, 那么那个“中位数的中位数”就是第k大的数。如果 i

K大的 数

K大的数