[理工] 資結 sort找最大,次大,最小

作者: ncdonalds123 (benben)   2019-01-29 21:29:42
https://i.imgur.com/bZGFQOg.jpg
請問第六題
a跟b小題我用bottom up 建max heap最後輸出root這樣可以時間O(n)
c小題我先存頭兩個數字,然後依序讀取,若有大於或小於這兩個數字的swap時間在O(n
)
這樣子寫會有哪裡有問題嗎,還是我完全搞錯題目意思了
麻煩大家了,謝謝
作者: moozkito (Once!)   2019-01-29 23:44:00
他要的是確定的數字吧舉例來說用bubble sort跑1iteration,最差比38次可以找到最大 不過想不到有什麼更好的
作者: nannnnn (nannnnn)   2019-01-30 00:09:00
我是用遞迴 取前面兩個數相比得兩數a1>a2 然後遞迴下去找n-2個數最大最小,再拿大比a1最小比a2,時間複雜度為T(n)=T(n-2)+3忘記說c小題ab小題我只會線性比38次找到QQT
作者: ncdonalds123 (benben)   2019-01-30 11:32:00
謝謝,看來就寫38次了,不知道他到底是想要我們回答什麼QQ
作者: FRAXIS (喔喔)   2019-01-30 11:50:00
b 小題不可能 38 吧https://cs.stackexchange.com/a/83056
作者: ncdonalds123 (benben)   2019-01-30 17:28:00
原本b是考慮寫75感謝樓上提供演算法
作者: nannnnn (nannnnn)   2019-01-31 17:26:00
耍二了 第二不可能38

Links booklink

Contact Us: admin [ a t ] ucptt.com