算法分析与实践 作业6
1、问题
用特定分治算法找出数组中第k大的元素。
2、解析
- |S1|=k，则m*就是所要找的第 k 小的数；
- |S1|>=k，归约为在S1中找第 k1 小的子问题，k 在子问题中相对位置不变，即k=k1
- |S1|<=k，归约为在S2中找 k2 位置的子问题，k2 相对于 S2 子问题和 k 相对 于 S 的关系，即 k2= k-|S1|-1。（在 S 中找 k，就是在 S2中找 k2）
3、设计
4、分析
5、源码
https://github.com/zhaozhiliangzzl/-/blob/master/%E7%89%B9%E5%AE%9A%E5%88%86%E6%B2%BB%E7%AE%97%E6%B3%95.cpp