×
解除綁定,重新設定系統帳號的密碼
您的系統帳號 ID:
您的系統帳號:
您的帳號暱稱:
設定新密碼:
設定新密碼:
×
請輸入要加入的「課程代碼」
請向開設課程的使用者索取「課程代碼」
分類題庫
解題動態
排行榜
討論區
競賽區
登入
註冊
發表新討論
解題報告
#13335: 三種解題思路
oo12374
(小屋)
學校 : 國立彰化高級中學
編號 : 41314
×
傳送站內訊息
傳給:
主題:
內容:
來源 : [125.231.99.143]
最後登入時間 :
2019-12-27 12:53:00
b542.
聽到這兩個人的身高,讓十萬人都驚呆了
--
104學年度
板橋高中
校內
資訊學科能力競賽
(二)
| From: [111.246.0.249] | 發表日期 : 2018-02-04 12:44
一
用bubble sort或selection sort,原本swap()的部分改成比較兩數的差距是否為k
⇒可能會超時
二
1 8 3 9 10, k=1
for i 0 to len(a)
if(a[a[i]])
找到了
a[a[i]+k]=True
a[a[i]-k]=True
1
2
3
4
5
6
7
8
9
10
True
True
True
True
i=3 a[i]=9的時候,找到相差為1的兩個數(8,9)
⇒ 這個方法只需要O(n)的time complexity
⇒ 但是題目有限制 0<=Ai<=2
31
-1,陣列大小可能需要(2
31
),
⇒ 很顯然的不能這樣做,可以用hash function來改進
這個方法可以這麼想,我知道你是誰了,可是不知道你在哪裡,存不存在,因此我把你的名字記下來,然後去找你
三
對陣列A排序,宣告兩個變數p=0,q=1
if a[q]-a[p]<k
q+=1
if a[q]-a[p]>k
p+=1
if(p==q)
q+=1
if a[q]-a[p]==k
return true
如果差距比k小,那麼就增加距離
如果差距比k大,那摩就縮小距離
⇒可行的解法, time complexity是O(nlgn)
結論
這裡提供三種思路,除了第三種方法,大家也可以試試看用hash來實現第二種方法,
如果有什麼疑問,歡迎提出來哦
ZeroJudge Forum