华师一附中OI组

标题: 求第k大元素 [打印本页]

作者: admin 时间: 2019-4-20 15:30
标题: 求第k大元素
给定一个数组假设10个元素，分别是6,3,7,5,9,8,1,2,0,4求其中第k大的元素
有一个很直观的做法就是先排序然后输出，这样很浪费，因为没有必要全部排序，
也有人会想到用选择排序做k次，或者冒泡k次，这样其实也有些浪费。
最好的做法是二分：假设k=3
1、第1个元素是6，把比6小的数字网左边换，比6的大的数字往右边换，这样1,2,0,4到了左边，7,9,8，到了右边，6 在第7位，数组变成了1,3,0,5,2,6,8,9,7
2、现在只需要在1,3,0,5,2,里面去找第3大的元素，继续

欢迎光临华师一附中OI组 (http://hsyit.cn/)