最新消息:点击查看大S的省钱秘笈

分治算法求N个数中第K小(大)的数

编程相关 Slyar 242浏览 0评论

文章作者:姜南(Slyar) 文章来源:Slyar Home (www.slyar.com) 转载请注明,谢谢合作。

恩,这个学期开算法课,跟着进度写写代码就好。这周讲分治,说到了求N个数中第K小(大)数的问题,写写看。

分治算法的复杂度是O(n),用到了快速排序的思路:先选取一个参考数进行一次快排,拿升序来说的话,快排之后左边所有数<参考数,右边所有数>参考数,然后根据左右部分各自包含元素的个数,计算要求的元素在哪个区间内(要求的元素或是左区间中的第k小数,或是右区间中第[k-j]小数,j为左区间的长度),然后递归求解。

本来pku 2104和pku 2761都是求第K小数的题,无奈用这个算法TLE,只能用后面的划分树或是其他复杂度更低的算法来做,以后再说吧。我这里只贴用这个算法做的,虽然交上去会TLE...

转载请注明:Slyar Home » 分治算法求N个数中第K小(大)的数

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

网友最新评论 (2)

  1. @felix021 恩,看看。我用scanf一样TLE...
    Slyar7年前 (2010-03-27)回复
  2. 快速划分只是理论上的O(n)。另外,TLE的原因可能是你用了cin/cout。 推荐一下我以前写的2篇: https://www.felix021.com/blog/read.php?1318 https://www.felix021.com/blog/read.php?1653
    felix0217年前 (2010-03-27)回复