Feng003

算法课课程作业

codeforces(2) DP(3) 图论(2) 基础数据结构(2) 字符串(1) 数据结构课程(1) 概率期望(1) 题解(6)

/ 注册

全部文章 / 算法课课程作业（共1篇）

找区间第k大（小）的数

问题：给定n个整数，如何用最快的方法求出第k大的数？　　我们当然可以对这n个整数排序然后直接输出第k大的数，时间复杂度为O(nlog n)。　　但是实际上我们可以用基于快速排序所用到的思想，在每一层递归中，随机选取一个数为基准值，把比它大的数交换到左半段，把其余的数和基准值自身一起作为右半段。在这...

区间第ｋ大

2020-04-01

0 873