第K个数字
本文最后更新于:2021年3月22日 上午
代码模板
1 |
|
代码原理
扫描+交换
第一步首先和之前的快速排序算法相同,首先在第一步的时候随机取一个位置,然后将这个位置的数字q[x]
记录下来,然后一个指针i
从前向后扫描数列,一个指针j
从后向前扫描数列,最后一般来说最后i
会在x
的位置停下,而j
会停在x的前一个。这样第一轮的排序就达成了,在q[x]
前面的数字都比q[x]
小,在q[x]
后面的数字都比它大。
位置排序
将整个数列分为Left
和Right
两部分,统计Left
和Right
的数量,如果pos
<Left的数量
,则说明需要的数字在Left
序列里面,这个时候只需要再次对Left
序列进行递归,如果数字在Right
序列中,则说明pos
的位置变成了第pos-[Left的数量]
个,然后只需要对右半边进行递归即可
结果
在不断进行递归操作后,将会只剩下pos
位置的数字,也就是第pos
个数字,这个时候返回的结果就是第pos
个数字了。
时间复杂度
第一次扫描的时候时间复杂度为n,第二次扫描的时候由于是扫描一半,所以最多也只有1/2n,然后依次下去就是1/4n,1/8n…,由数学知识可以得出,n+1/2n+… 最多不会超过2n,所以复杂度为O(n)
。
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!