PTT數位生活區 / C_and_CPP (C/C++)

[問題] 找兩個已排序陣列共同的數

看板C_and_CPP (C/C++)作者 (喵貓 loves fish)時間16年前 (2009/12/11 00:37), 編輯推噓3(3推 0噓 10→)
留言13則, 4人參與, 最新討論串1/3 (看更多)
( *[1m *[m 為色碼，可以按 Ctrl+V 預覽會顯示的顏色 ) ( 未必需要依照此格式，文章條理清楚即可 ) 遇到的問題： (題意請描述清楚) TLE http://zerojudge.tw/ShowProblem?problemid=d136 寫的改進版本第一個測資變快了 但是第二個測資還是TLE(1s) 希望得到的正確結果： 要如何加速？ 我本身是從兩個陣列的第一個元素開始　如果比較小的那邊就作 binary search找到大於等於另外一個陣列的那個元素　直到底 程式跑出來的錯誤結果： 開發平台： (例: VC++ or gcc/g++ or Dev-C++, Windows or Linux) 有問題的code： (請善用置底文標色功能) http://nopaste.csie.org/2771e 補充說明： -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.228.104.249
推
12/11 00:45, , 1F
1. 不要用 scanf, 用 getchar 來處理 input
12/11 00:45, 1F
→
12/11 00:46, , 2F
2. binary search 不見得比較快
12/11 00:46, 2F
→
12/11 00:47, , 3F
比如說一邊是 1 3 5 7 9, 一邊是 2 4 6 8 10
12/11 00:47, 3F
→
12/11 00:47, , 4F
binary search 沒辦法幫他跳很遠, 反而 overhead 變高了
12/11 00:47, 4F
→
12/11 00:55, , 5F
我擺過一些情形　好像比較稀疏的時候bs才比較快
12/11 00:55, 5F
→
12/11 00:55, , 6F
可是我也想不太到別的方法~"~
12/11 00:55, 6F
→
12/11 00:55, , 7F
一個一個往上找和bs以外的@@?
12/11 00:55, 7F
推
12/11 00:57, , 8F
真的要 bs 的話, 請用 stack 版本, function call overhead
12/11 00:57, 8F
→
12/11 00:57, , 9F
在呼叫多次時也是很可觀的
12/11 00:57, 9F
→
12/11 00:58, , 10F
stack -> loop ...... 我在講什麼呀我 該睡了 XD
12/11 00:58, 10F
→
12/11 02:08, , 11F
擺2個哨兵跑一個迴圈
12/11 02:08, 11F
推
12/11 21:32, , 12F
這一題問的其實就是 STL 中 set_intersection 的實作
12/11 21:32, 12F
→
12/11 23:09, , 13F
抱歉我嫩嫩的 聽不太懂呢 = ="
12/11 23:09, 13F
‣ 更多 tw00088437 的文章
文章代碼(AID): #1B8IErTr (C_and_CPP)
C_and_CPP 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 tw00088437 的文章
文章代碼(AID): #1B8IErTr (C_and_CPP)