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

看板Grad-ProbAsk作者 (benben)時間6年前 (2019/01/29 21:29), 編輯推噓3(3推 0噓 11→)
留言14則, 4人參與, 6年前最新討論串1/1
https://i.imgur.com/bZGFQOg.jpg
請問第六題 a跟b小題我用bottom up 建max heap最後輸出root這樣可以時間O(n) c小題我先存頭兩個數字，然後依序讀取，若有大於或小於這兩個數字的swap時間在O(n ) 這樣子寫會有哪裡有問題嗎，還是我完全搞錯題目意思了 麻煩大家了，謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.71.108.194 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1548768584.A.C75.html
→
01/29 23:44, 6年前 , 1F
他要的是確定的數字吧
01/29 23:44, 1F
→
01/29 23:44, 6年前 , 2F
舉例來說用bubble sort跑1iteration，最差比38次可以找
01/29 23:44, 2F
→
01/29 23:44, 6年前 , 3F
到最大 不過想不到有什麼更好的
01/29 23:44, 3F
推
01/30 00:09, 6年前 , 4F
我是用遞迴 取前面兩個數相比得兩數a1>a2 然後遞迴下去找
01/30 00:09, 4F
→
01/30 00:09, 6年前 , 5F
n-2個數最大最小，再拿大比a1最小比a2，時間複雜度為T(n)
01/30 00:09, 5F
→
01/30 00:09, 6年前 , 6F
=T(n-2)+3
01/30 00:09, 6F
推
01/30 00:10, 6年前 , 7F
忘記說c小題
01/30 00:10, 7F
→
01/30 00:12, 6年前 , 8F
ab小題我只會線性比38次找到QQT
01/30 00:12, 8F
→
01/30 11:32, 6年前 , 9F
謝謝,看來就寫38次了,不知道他到底是想要我們回答
01/30 11:32, 9F
→
01/30 11:32, 6年前 , 10F
什麼QQ
01/30 11:32, 10F
推
01/30 11:50, 6年前 , 11F
b 小題不可能 38 吧
01/30 11:50, 11F
→
01/30 11:54, 6年前 , 12F
01/30 11:54, 12F
→
01/30 17:28, 6年前 , 13F
原本b是考慮寫75感謝樓上提供演算法
01/30 17:28, 13F
→
01/31 17:26, 6年前 , 14F
耍二了 第二不可能38
01/31 17:26, 14F
‣ 更多 ncdonalds123 的文章
文章代碼(AID): #1SK5L8nr (Grad-ProbAsk)