[問題] 同時尋找最小和第二小的數字(修改過)

看板C_and_CPP (C/C++)作者atoi (atoi)時間16年前 (2010/04/09 00:12)推噓5(5推 0噓 16→)

留言21則, 8人參與討論串1/1

( *[1m *[m 為色碼，可以按 Ctrl+V 預覽會顯示的顏色 ) ( 未必需要依照此格式，文章條理清楚即可 ) 遇到的問題： (題意請描述清楚) 不好意思又來問問題ㄟ就是呢有個題目要找一堆數字當中第二小的數字然後比較次數是 n + lgn(取上界) - 2 題目有個hint寫說同時也會找到最小的但我想了一個應該是最多 n 次的方法不過我不知道方法對不對, 或是錯很大, 想來問一下就是一開始先兩兩一組比較, 每組得到小的數字後再用這些小的數字在兩兩比較 (一直這樣下去...) 最後會得到兩個數字(假設叫x,y好了,且x<=y), 這時就停止, 但還要再比一次就是看 x 一開始是兩兩一組時是從哪一組得來的, 假設該組的另一個數字是z 然後將y和z比較, 若y<z則最小和第二小分別為x和y,否則是x和z 而若x已經等於y那就不用再比最後一次我舉個例子好了: 5 1 2 8 0 3 6 4 <-- 比較次數: 4 (1 5) (2 8) (0 3) (4 6) \ \ <-- 比較次數: 2 (1 2) (0 4) / <-- 比較次數: 1 (0 1) (1<3) <-- 比較次數: 1 答案: 0和1 total: 4+2+1+1=8 有畫斜線表示小的數字從一組哪來, 最後沿著斜線找到最上層的數字就可以比較最後一次了我是想說數字若夠小一定最後會留下來,太大的就直接不理會但是最小的數字或許剛開始比較會忽略了另一個數字所以再比最後一次ㄟ...不知道這樣對不對, 有錯請指教, 謝謝了, 也感謝耐心的看完喔我後來有想到了, 應該要沿著斜線然後每組的另一個數字"都比較" 這樣的話就會是n +lgn(取上界) - 2 了也有順便google一下, 應該是這樣沒錯謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.224.134.150

→

atoi

04/09 00:26, , 1^F

04/09 00:26, 1^F

→

htymrednuht

04/09 00:31, , 2^F

04/09 00:31, 2^F

→

tw00088437

04/09 00:32, , 3^F

04/09 00:32, 3^F