作者ncdonalds123 (benben)
看板Grad-ProbAsk
标题[理工] 资结 sort找最大,次大,最小
时间Tue Jan 29 21:29:42 2019
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://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1548768584.A.C75.html
1F:→ moozkito: 他要的是确定的数字吧 01/29 23:44
2F:→ moozkito: 举例来说用bubble sort跑1iteration,最差比38次可以找 01/29 23:44
3F:→ moozkito: 到最大 不过想不到有什麽更好的 01/29 23:44
4F:推 nannnnn: 我是用递回 取前面两个数相比得两数a1>a2 然後递回下去找 01/30 00:09
5F:→ nannnnn: n-2个数最大最小,再拿大比a1最小比a2,时间复杂度为T(n) 01/30 00:09
6F:→ nannnnn: =T(n-2)+3 01/30 00:09
7F:推 nannnnn: 忘记说c小题 01/30 00:10
8F:→ nannnnn: ab小题我只会线性比38次找到QQT 01/30 00:12
9F:→ ncdonalds123: 谢谢,看来就写38次了,不知道他到底是想要我们回答 01/30 11:32
10F:→ ncdonalds123: 什麽QQ 01/30 11:32
11F:推 FRAXIS: b 小题不可能 38 吧 01/30 11:50
13F:→ ncdonalds123: 原本b是考虑写75感谢楼上提供演算法 01/30 17:28
14F:→ nannnnn: 耍二了 第二不可能38 01/31 17:26