Re: [問題] 貌似Facebook面試題目
看板Prob_Solve (計算數學 Problem Solving)作者saladim (殺拉頂)時間12年前 (2012/03/17 19:38)推噓3(3推 0噓 12→)留言15則, 4人參與討論串2/5 (看更多)
※ 引述《saladim (殺拉頂)》之銘言：
: 有人跟我說這是一提FB的面試題目, 想了一下想不太出合適的解法, 題目如下:
: 給一個sorted array, 找出array裡面有沒有某兩個元素加起來等於另外一個元素,
: 有的話請列印出來, 沒有的話請回答沒有.
: 嘗試利用 sorted元素大小關係跟binary search去做, 但是想不出來阿!!!!
: 請各位大大提供一下意見.....感激不盡.....
剛回來 看到推文 先來簡短回應一下 ORZ , 自己當然有一些想法 敘述如下:
根據原來的題目 可以得到以下訊息(假設元素不重複):
假設 a, b, c為所求(a,b,c都是陣列內的元素), 則
1. a+b=c,
2. a<b<c,
3. 0 <= i < j < k <= MAX_NUM, 其中i j k為 a b c的索引值.
虛擬碼:
for i = 0 to MAX-2
{
for j = i+1 to MAX-1
{
ans = binary_search( a[i]+a[j] );
if 0 <= ans && ans < MAX_NUM
printf i,j ans
}
}
這樣可以印出滿足 a+b=c 的所有pair. 我想這個時間複雜度是 O(N^2 * logN) (對吧??)
但是呢 看到 N^2就有點不舒服 然後又說是FB的面試題 所以根據小弟的崇洋媚外心理
覺得應該會有 N*logN 或是 logN*logN之類的方法 祇是我想不到而已 XD
以上!!!
那我先去研究一下3SUM problem......歡迎大家來討論討論~~~~
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.43.203.126
→
03/17 21:24, , 1F
03/17 21:24, 1F
→
03/17 21:29, , 2F
03/17 21:29, 2F
→
03/17 22:07, , 3F
03/17 22:07, 3F
→
03/17 22:07, , 4F
03/17 22:07, 4F
→
03/17 22:11, , 5F
03/17 22:11, 5F
→
03/17 22:12, , 6F
03/17 22:12, 6F
→
03/17 22:17, , 7F
03/17 22:17, 7F
推
03/18 02:47, , 8F
03/18 02:47, 8F
推
03/18 03:27, , 9F
03/18 03:27, 9F
→
03/18 03:27, , 10F
03/18 03:27, 10F
→
03/18 03:28, , 11F
03/18 03:28, 11F
推
03/18 03:49, , 12F
03/18 03:49, 12F
→
03/18 03:50, , 13F
03/18 03:50, 13F
→
03/18 03:50, , 14F
03/18 03:50, 14F
→
03/18 03:51, , 15F
03/18 03:51, 15F
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
