Re: [問題] 貌似Facebook面試題目
看板Prob_Solve (計算數學 Problem Solving)作者DJWS (...)時間12年前 (2012/03/18 23:44)推噓0(0推 0噓 0→)留言0則, 0人參與討論串3/5 (看更多)
※ 引述《saladim (殺拉頂)》之銘言：
: 有人跟我說這是一提FB的面試題目, 想了一下想不太出合適的解法, 題目如下:
: 給一個sorted array, 找出array裡面有沒有某兩個元素加起來等於另外一個元素,
: 有的話請列印出來, 沒有的話請回答沒有.
: 嘗試利用 sorted元素大小關係跟binary search去做, 但是想不出來阿!!!!
: 請各位大大提供一下意見.....感激不盡.....
這邊提供一個另類的想法。
想像一個二維陣列 sum[i][j] = array[i] + array[j]
可以發現往右往下 sum 會變大，往左往上 sum 會變小，
其實 sum 就是一個排序過的二維陣列。
在 sum 裡面做 binary search 需要 O(N) 時間。
套用前面 LPH66 與 stimim 板友推文裡的解法，
窮舉 array 的每一個數字，在 sum 裡面二分搜尋，
總共就是 O(NN) 時間了。
那麼能不能更快呢？我也不知道...
窮舉 array 的每一個數字，是由小到大窮舉的話，
每一個數字在 sum 裡面的二分搜尋路線，就是逐漸偏右、偏下，
這些路線應該會有很多地方重疊，
如果可以把重疊的路線省略掉的話，應該可以更快吧？
以上
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.230.130.247
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
