PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] 貌似Facebook面試題目

看板Prob_Solve (計算數學 Problem Solving)作者LPH66 (-858993460)時間12年前 (2012/03/19 01:05)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串4/5 (看更多)

※ 引述《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