美文网首页
算法-Review

算法-Review

作者: by666 | 来源:发表于2020-04-16 16:56 被阅读0次

    一组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次找出


    相关文章

      网友评论

          本文标题:算法-Review

          本文链接:https://www.haomeiwen.com/subject/hhldvhtx.html