现在的位置: 首页 > 综合 > 正文

选择N个数中第k个最大者——选择问题(selection problem)

2013年08月05日 ⁄ 综合 ⁄ 共 949字 ⁄ 字号 评论关闭

问题:设有一组N个数而要确定其中第k个最大者。

 

solution  0: 

         最简单的方法当然就是将N个数读进数组里头,然后降序排序,返回a[k-1]即可。

 

solution  1:

         把前k个元素读入数组,并以降序排序。接着,将剩下的元素逐个读入。当新元素被读到时,如果它小于数组中的第k个元素则忽略,否则将其放到正确的位置,同时将数组的最后一个元素挤出数组。当算法终止时,位于第k个位置的元素即为所求。

实现如下:

 

solution 1相比solution 0,空间上省了一些,但时间消耗明显要大一些。

抱歉!评论已关闭.