I tried this before. I got an NP question. Damn i didn't even try to solve that...

I guess this is a good reminder

of ?

of the problem that's waiting for you!

dapudding > < no~~~ no NP questions

dapudding here's one for you. It's easy and you may also think about how you explain why your algo is correct

Given a sorted list of numbers

find two numbers a and b among them, that a-b=k given some k

there's an O(n) solution

e.g., 1 2 4 6 11 13 17 20

k = 6

then a = 11 and b = 17

Have fun & good night

..........orz

i only came up with O(n^2) one: start with the numbers next to each other and check their difference. Then check the numbers that with one number between them, and two numbers between them and so on....

wait...the complexity should be n! .....? God I suck at analyze this

dapudding: it's a "sorted" list

n^2 吧. n! 就直接掛電話了

幹嘛這樣QQ 為什麼不是n! ? 第一次scan跑n-1個element...第二次只要n-2個阿...最後一次不是只要看第一個跟最後一個差多少嗎QQ 就我的解法來說

是說 我知道兩個數中間相差只要超過k就可以不用看了...但還想不到怎麼可以利用這點...拆成小的list?

n-1 + n-2 + n-3 + ... 2 + 1 =???

阿 好啦QQ我懂了 大歐大歐

欸幹 我是智障欸 好想把對話刪掉喔 n!明明就是階乘......

不玩了 我要去麥當勞打工

a b ... c d ... <- the sorted list
known a<b<c<d
if c-a<k while d-a >k
do I have to check if c-b==k???

來不及了我人已經在麥當勞哭了

int ptr_a=0;
int ptr_b=1;

while(ptr_b < list.length){
int diff = list[ptr_a] - list[ptr_b];
if(diff == k)
printf("a= %d, b= %d", list[ptr_a], list[ptr_b]);
else if(diff > k) ptr_a=ptr_b-1 else ptr_b +=1 }

小豆你有沒有覺得你很適合當老師?其實你超有耐心的XD

阿沒取絕對值

dapudding: 我只教聰明的孩子 (grin) 話說有大薯嗎？

方向對了，但我還要仔細看看

只要大薯就可以請的老師也是挺划算的XDDDDDDDD