分治法

两个已排好顺序的序列A,B 长度为m,n,寻找第k大的数

  —第一次取出a[k/2], b[k/2]两个数比较

    —如果两个数相邻,那么找到了

      较大的数的前一个是比较小的数小,较小的数的后一个比较大的数大

    —如果两个数不相邻,那么

      k/4地找

寻找最大值和最小值:比较次数 3n/2-2

  —先两两进行比较,得到胜者组和败者组:n/2

  —分别在组内找到最大值和最小值:2* (n/2 - 1)

寻找最大值和次大值:比较次数n+logn

  —先找到最大值,利用胜者树:T(n) = T(n/2) + n/2 = n-1

    —先两两比较:n/2

    —递归下去:T(n/2)

  —按生成的递归树,由胜者路径下降找到路径中最大的(除了最大值):logn

寻找众数

  —绝对众数

    —顺序消去不同的数

  —普通众数

    —排序

    —统计

      —数组

      —散列

原文地址:https://www.cnblogs.com/siyudemo/p/3133537.html