歡迎來(lái)到 常識(shí)詞典網(wǎng) ， 一個(gè)專(zhuān)業(yè)的常識(shí)知識(shí)學(xué)習(xí)網(wǎng)站！
[ Ctrl + D 鍵 ]收藏本站
如果找到第一個(gè)數(shù)需要多少次comparison? 在找第一次的時(shí)候你肯定會(huì)miss第2個(gè)最大的，那找到第2個(gè)最大的你會(huì)做多少次比較。可以把算法復(fù)雜度提高到比O(n+lgn)還少嗎？
4 個(gè)答案答案 1：
呵呵，但是2位你們忽略了建立-eap的時(shí)候的比較次數(shù)呀。不要認(rèn)為它很少，所以你們的答案不對(duì)答案 2：
找到最大的數(shù)-x需要比較n-1次第二大的數(shù) 應(yīng)該是從與-x比較過(guò)的數(shù)中找出.與-x比較過(guò)的數(shù)算logn（上取整） 同理得到第二大的數(shù)是logn（上取整）-1
一共就是n+logn-2
答案 3：
用堆排序，時(shí)間復(fù)雜度是2lgn
答案 4：
只是找兩個(gè)最大的而已，不需要把所有數(shù)字都排序。。。
遍歷一趟就夠。
下一篇:-301要多久生效？ 下一篇 【方向鍵 ( → )下一篇】
上一篇:被提問(wèn)或者提問(wèn)收到回答會(huì)有e-il提醒嗎？ 上一篇 【方向鍵 ( ← )上一篇】
快搜
