如何在一大堆数字里面寻找最大的2个数?
2012-01-19 18:03:14   来源：   点击：

如果找到第一个数需要多少次comparison? 在找第一次的时候你肯定会miss第2个最大的，那找到第2个最大的你会做多少次比较。可以把算法复杂度提高到比O(n+lgn)还少吗？

4 个答案

• 答案 1：

  呵呵，但是2位你们忽略了建立heap的时候的比较次数呀。不要认为它很少，所以你们的答案不对

• 答案 2：

  找到最大的数max需要比较n-1次第二大的数 应该是从与max比较过的数中找出.与max比较过的数算logn（上取整） 同理得到第二大的数是logn（上取整）-1

  一共就是n+logn-2

• 答案 3：

  用堆排序，时间复杂度是2lgn

• 答案 4：

  只是找两个最大的而已，不需要把所有数字都排序。。。

  遍历一趟就够。