如何在一大堆数字里面寻找最大的2个数?

阅读 :124

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

答案 1：

答案 2：

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

一共就是n+logn-2

答案 3：

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

答案 4：

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

遍历一趟就够。

下一篇:-301要多久生效？ 下一篇 【方向键 ( → )下一篇】

上一篇:被提问或者提问收到回答会有e-il提醒吗？ 上一篇 【方向键 ( ← )上一篇】