#13335: 三種解題思路
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<=231-1,陣列大小可能需要(231),
⇒ 很顯然的不能這樣做,可以用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來實現第二種方法,
如果有什麼疑問,歡迎提出來哦
#40353: Re: 三種解題思路
b542. 聽到這兩個人的身高，讓十萬人都驚呆了
--
104學年度板橋高中校內資訊學科能力競賽（二）
| From: [123.252.121.18] |
發表日期
:
2024-05-13 14: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<=231-1,陣列大小可能需要(231),
⇒ 很顯然的不能這樣做,可以用hash function來改進
這個方法可以這麼想,我知道你是誰了,可是不知道你在哪裡,存不存在,因此我把你的名字記下來,然後去找你
三
對陣列A排序,宣告兩個變數p=0,q=1
if a[q]-a[p]
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