kth element

第K小算法

问题

给定长度为$n$的序列$a$和整数$k\in[1,n]$，求出$a$中第$k$小的数。

解法一：半个快排

使用快排思路，每次随机找一个数当作pivot，小于pivot放左边，大于pivot放右边，然后根据$k$的大小决定去左边还是右边查找。复杂度期望$O(n)$，最坏$O(n^2)$。

代码

解法二：median of medians

还是使用快排思路，这次用一个骚操作：

假设当前在找$[l,r]$内的第$k$小，即solve(l, r, k)。尝试找当前序列的pivot时，先将所有数$5$个一组分组，得到$n/5$个长度为$5$的子序列，对于每个子序列，找出中位数（这是$O(1)$的），得到一个长度为$n/5$的中位数序列，再递归调用solve(1, n/5, n/10)找到这个中位数序列的中位数，作为pivot。

这个pivot一定不小于$n/10$个中位数，也就是说不小于$\frac{3}{10}n$的数，同理也不大于$\frac{3}{10} n$的数。

写出递归表达式：

$$T(n) = T(\frac{7}{10} n) + T(\frac{1}{5} n) + O(n)$$

可以证明$T(n) = O(n)$，证明如下：

• $n=1$时，成立；

• 假设$n\leq k-1$时满足$T(n) \leq B\cdot n$，则

  $$\begin{aligned}T(k) &= T(0.7 k) + T(0.2 k) + Ck\\ &= 0.7B k + 0.2 B k + Ck\\ &= (0.9B + C) k \end{aligned}$$

  只要$0.9B + C \leq B$就可以，也就是说$B\geq 10C$就行。取任意满足条件的$B$即可得出$T(n)=O(n)$。

不过观察到$B\sim 10C$，也就是说算法有个$10$的常数，可能常数会比较大。随机情况下，差不多慢三倍。

代码