Re: [問題] 貌似Facebook面試題目
※ 引述《DJWS (...)》之銘言：
: 這邊提供一個另類的想法。
: 想像一個二維陣列 sum[i][j] = array[i] + array[j]
: 可以發現往右往下 sum 會變大，往左往上 sum 會變小，
: 其實 sum 就是一個排序過的二維陣列。
: 在 sum 裡面做 binary search 需要 O(N) 時間。
: 套用前面 LPH66 與 stimim 板友推文裡的解法，
: 窮舉 array 的每一個數字，在 sum 裡面二分搜尋，
: 總共就是 O(NN) 時間了。
: 那麼能不能更快呢？我也不知道...
: 窮舉 array 的每一個數字，是由小到大窮舉的話，
: 每一個數字在 sum 裡面的二分搜尋路線，就是逐漸偏右、偏下，
: 這些路線應該會有很多地方重疊，
: 如果可以把重疊的路線省略掉的話，應該可以更快吧？
: 以上
嘛...其實我想到的做法有點不太對稱
我是一次固定一個數字 另一個數字用類似 merge sort 的方式往後掃
虛擬碼大概像這樣
for(i = 0 ... n-1)
{
j = 0
k = 0
while(j < n && k < n)
{
if(array[i] + array[j] < array[k]) j++;
else if(array[i] + array[j] > array[k]) k++;
else {print Found [i] + [j] = [k]; exit}
}
}
print Not Found
中間那層 while 因為 j++ 和 k++ 最多各 n 次 所以是 O(n)
因此全部就是 O(n^2) 這樣
說是不對稱是因為我列舉的是 [i] 上面那個列舉的是 [k] 這樣而已...
--
1985/01/12 三嶋鳴海 1989/02/22 優希堂悟 1990/02/22 冬川こころ 1993/07/05 小町
つぐみ 歡迎來到 1994/05/21 高江ミュウ 1997/03/24 守野いづみ 1997/03/24 伊野瀬
チサト 1998/06/18 守野くるみ 打越鋼太郎的 1999/10/19 楠田ゆに 2000/02/15 樋口遙
2002/12/17 八神ココ 2011/01/11 HAL18於朱倉岳墜機 ∞與∫的世界 2011/04/02 茜崎空
啟動 2012/05/21 第貮日蝕計畫預定 2017/05/01~07 LeMU崩壞 2019/04/01~07 某大學合宿
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.28.91
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 4 之 5 篇)：