辕门射虎 - 算法题轩辕春秋文化论坛 20周年

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	好帖奖励