<< 上一主题 | 下一主题 >>

投票 交易 悬赏 活动

MMM 组别 百姓 级别 在野武将 功绩 0 帖子 44 编号 270202 注册 2008-3-8

#1 发表于 2008-10-3 06:35 资料 短消息 只看该作者 算法题 设A为一个有n个数的无序可重复数列 要取得这个数列里第k小的那个数 即把A排序后 脚标为k的那个元素 先提醒一下 排序本身的时间代价是不可能只用O(n)的 所以就需要想不排序就获得结果的算法 [广告] 真诚支持说岳，携手共创辉煌

MMM 组别 百姓 级别 在野武将 功绩 0 帖子 44 编号 270202 注册 2008-3-8

#2 发表于 2008-10-3 06:36 资料 短消息 只看该作者 很久没有来了。。。大家还好吗 [广告] 《精忠报国岳飞传完整版》火热发布

bod 组别 百姓 级别 在野武将 功绩 0 帖子 4 编号 292972 注册 2008-10-1

#3 发表于 2008-10-3 08:02 资料 短消息 只看该作者 1、取决于特定的环境，排序可以在O(n)的情况下完成，比如，待排序的数是在某个可接受范围内的整数 2、普通情况，这个问题是经典的快速选择问题，分治算法的经典表现，步骤如下： step1：从A中随机选择一个数P； step2：从A中挑选出所有大于P的数； step3：如果大于P的数的数量是k-1，那么p就是结果，算法结束； step4：如果大于P的数的数量小于k-1，到step6； step5：如果大于P的数的数量大于k-1，到step7； step6：将小于P的数组成新的数组A'，并回到第一步，递归的对这个数组执行本算法，但是寻找的目标修改为n - k step7：将大于P的数组成新的数组A'，并回到第一步，递归的对这个数组执行本算法 C++代码可以参考任何一个STL的算法nth_element 算法的平均时间复杂度是O(n) 本帖最近评分记录 青木风亮 2008-10-5 23:50 +50 好帖奖励 [广告] 真诚支持说岳，携手共创辉煌

投票 交易 悬赏 活动

当前时区 GMT+8, 现在时间是 2025-2-2 05:45
京ICP备2023018092号 轩辕春秋 2003-2023 www.xycq.org.cn