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

[問題] 貌似Facebook面試題目

看板Prob_Solve (計算數學 Problem Solving)作者 (殺拉頂)時間12年前 (2012/03/17 12:11), 編輯推噓5(5推 0噓 9→)
留言14則, 11人參與, 最新討論串1/5 (看更多)
有人跟我說這是一提FB的面試題目, 想了一下想不太出合適的解法, 題目如下: 給一個sorted array, 找出array裡面有沒有某兩個元素加起來等於另外一個元素, 有的話請列印出來, 沒有的話請回答沒有. 嘗試利用 sorted元素大小關係跟binary search去做, 但是想不出來阿!!!! 請各位大大提供一下意見.....感激不盡..... -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 114.43.203.126
推
03/17 12:31, , 1F
3 sum problem 的小變形, google 一下就有, O(n^2) 解法
03/17 12:31, 1F
→
03/17 12:58, , 2F
?? 要等於的那個元素不是給定的 是陣列內要找出來的
03/17 12:58, 2F
→
03/17 12:58, , 3F
等等我去辜狗一下
03/17 12:58, 3F
→
03/17 13:28, , 4F
你說想不出來是任何一個基本解都想不出來嗎?
03/17 13:28, 4F
→
03/17 14:43, , 5F
再怎麼想不到解好歹最簡單的 O(n^3) 的做法應該要想得到...
03/17 14:43, 5F
推
03/17 14:47, , 6F
O(n^2) 的提示: 兩層迴圈的其中一層是固定陣列某個元素
03/17 14:47, 6F
→
03/17 14:47, , 7F
當做加的其中之一
03/17 14:47, 7F
→
03/17 16:25, , 8F
固定沒錯，但應該是當作如何移動索引的判斷？
03/17 16:25, 8F
→
03/17 16:53, , 9F
給定和的話，可以在 O(n) 找到兩個元素
03/17 16:53, 9F
→
03/17 21:24, , 10F
包含負數嗎?
03/17 21:24, 10F
推
03/22 00:09, , 11F
N^2logN 再加上cut 會過嗎?
03/22 00:09, 11F
推
03/23 08:31, , 12F
03/23 08:31, 12F
→
03/23 12:44, , 13F
原來已經有人證出lower bound了..
03/23 12:44, 13F
推
03/26 00:05, , 14F
同Stimim大，可以在O(n)完成。
03/26 00:05, 14F
‣ 更多 saladim 的文章
文章代碼(AID): #1FP0xbjA (Prob_Solve)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 saladim 的文章
文章代碼(AID): #1FP0xbjA (Prob_Solve)