作者bleed1979 (十三)
看板C_and_CPP
標題Re: [問題] 找兩個已排序陣列共同的數
時間Sat Dec 12 00:18:44 2009
※ 引述《tw00088437 (喵貓 loves fish)》之銘言：
: ( *[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
: 補充說明：
algo
1.set x and y to index 0 for 2 number series A and B
2.cmpare 2 number series
2.1 if A[x]==B[y], count add 1, then x add 1 and y add 1
2.2 if A[x]<B[y], x add 1
2.3 if A[x]>B[y], y add 1
2.4 if x equals size of A, go to 4.
2.5 if y equals size of B, go to 4.
3.go to 2. and do compare again
4.output value of count
抱歉，我稍微修改一下，這應該可以了
--
World of bleed1979
http://bleed1979.myweb.hinet.net/
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.32.177.97
※ 編輯: bleed1979 來自: 114.32.177.97 (12/12 00:25)
推 tw00088437:咦 這是我第一次寫的版本啊...我以為O(n)可以過 結果 12/12 00:45
→ tw00088437:TLE... 12/12 00:45
→ yoco315:有趣耶.. 這樣還不夠快... 我來試試看... 12/12 00:55
推 LordPhoenix:我光io就tle了.. 12/12 01:23
推 tw00088437:我在基本版過了 但是也比前幾名慢一大截 12/12 01:43
→ tw00088437:去進階版就真的TLE了.. 12/12 01:43
→ yoco315:靠北.. 我基本過了.. 進階第二點 wa.. 拎良勒... 12/12 01:47
→ yoco315:金度爛這種在io上咬時間題目 = =" 12/12 01:48
→ yoco315:問題是我連答案都錯的.. 沒資格說話.. 12/12 01:48
→ bleed1979:AC了 這個演算法是對的 空間複雜度只需要O(m) 12/12 01:51
推 tw00088437:嗯我也看到b大AC了 = = 可是我好像也是這樣寫的啊Orz 12/12 01:52
→ bleed1979:第二排的數可以邊讀入邊比較，不用再開一個陣列 12/12 01:52
→ tw00088437:哦哦!!!! 這我試試看@@!! 12/12 01:53
推 tw00088437:*** 第 1 點 (1%)：AC (4ms, 272KB) 12/12 02:28
→ tw00088437:*** 第 2 點 (99%)：TLE (1s) 12/12 02:28
→ tw00088437:呃...請問一下b大我哪裡寫錯@@ 還是TLE 12/12 02:29
→ yoco315:大概是 scanf 吧.... XD 12/12 02:30