一组N个乱序数中寻找第K大的数
冒泡或者简单排序(时间复杂度:O(K * N))
for(int i == 0 ; i < K ; i ++){
for(int j == 0; j < N.count ; j ++){
if( N[0] < N[1] ){
交换位置
}
}
}
堆排序
堆排序时间复杂度为nlogn,第K大的数,二叉树只取K个,最深最后一个就是第K大的数(时间复杂度:O(NlogK))
快速排序
随机选一个数m,把比m大的放左边,比m小的放右边。如果比m大的总数,正好等于N-K,则m就是第K大的数,最好时间复杂度(O(N))
如果比m大的总数>K,去除m的数,进行上一步操作,直到m大的总数< K , 这时候选中的m就是第K大的数
有64匹马,8个赛道,最少跑多少次能找出跑最快的4匹马
分为8组,每组最后4匹淘汰,剩下32匹(8)
以上8组的第一名比赛一次,淘汰最后4名所在的组,剩下16匹(1)
此时能确定第一名A1,假设A1>B1>C1>D1,D是最慢的一组,则B4,C3,C4,D2,D3,D4不可能为前4,淘汰
A1 B1 C1 D1
A2 B2 C2 D2
A3 B3 C3 D3
A4 B4 C4 D4
剩下A1,A2,A3,A4,B1,B2,B3,C1,C2,D1
D1和A2,A3,A4,B2,B3,C2比一次,假如D1是最快的,则最快的4匹马就是A1,B1,C1,D1(1)///总共10次找出
假如D1不是最快的,就让A2,A3,A4,B2,B3,C2和B1,B2比一次,选出3名,则得到4匹最快的马 ///总共11次找出
网友评论