阅读: 118
如果找到第一个数需要多少次comparison? 在找第一次的时候你肯定会miss第2个最大的，那找到第2个最大的你会做多少次比较。可以把算法复杂度提高到比O(n+lgn)还少吗？
4 个答案答案 1：
呵呵，但是2位你们忽略了建立-eap的时候的比较次数呀。不要认为它很少，所以你们的答案不对答案 2：
找到最大的数-x需要比较n-1次第二大的数 应该是从与-x比较过的数中找出.与-x比较过的数算logn（上取整） 同理得到第二大的数是logn（上取整）-1
一共就是n+logn-2
答案 3：
用堆排序，时间复杂度是2lgn
答案 4：
只是找两个最大的而已，不需要把所有数字都排序。。。
遍历一趟就够。
分享常识给亲友.
下一篇:蜱虫会飞不？ 下一篇 【方向键 ( → )下一篇】
上一篇:人们喜欢把自己的价值观强加给别人？ 上一篇 【方向键 ( ← )上一篇】
快搜