Re: [問題] 程式考試時的拿捏

作者: Feis (永遠睡不著 @@)   2015-07-14 11:59:44
※ 引述《EdisonX (卡卡獸)》之銘言:
: 單純想討論算法。
: 1. sort (number ) , O(nlogn)
: 2. i = 0 : n-1
: (2.1) if( number[i] ) > target ) goto end
: (2.2) slack = target - number[i] ;
: (2.3) search ( number + i + 1, number + n , i)
: 這種算法整體應該也還是 O(nlogn) , 概要約如下。
<deleted>
: 不知道有沒有更好的作法? 另若是改成 (3個數之合) , (4個數之合) 為target 的話 ,
: 我也死在牆上了 XD
假設已經排完序了,題目也保證一定有一組解,且只需要找出一組解.
那應該是夾起來就好 ?
auto numbers = std::array<int, 4>{2, 7, 11, 15};
int target = 9;
int l = 0;
int r = numbers.size() - 1;
int sum;
do {
sum = numbers[l] + numbers[r];
if (sum > target) {
r
作者: cutekid (可愛小孩子)   2015-07-14 12:07:00
大推(Y)
作者: EdisonX (卡卡獸)   2015-07-14 13:03:00
推 ... 這方法確實較佳。
作者: cobrasgo (人魚線變成鮪魚線,超帥)   2015-07-14 18:11:00
有排序這個假設會不會太強了?
作者: EdisonX (卡卡獸)   2015-07-14 21:32:00
@cobrasgo , 沒排序過的話做 struct 記 idx 應該不難 ,這篇所提的方法還是十分有效的。
作者: ciphero (奶油焗蛋餃...:))   2015-07-14 21:45:00
ㄜㄜ...怎麼到後來大家都覺得應該是有排序的~~@@其實原題目是沒有排序的https://leetcode.com/problems/two-sum/只不過剛好題目舉的例子看起來是有排序而已
作者: EdisonX (卡卡獸)   2015-07-14 21:55:00
耶 ... 我的意思是 , 這題目就算沒排序過 , 也可以轉換成有排序過的 , 複雜度頂多變成 O(nlogn) , 還是有效的解法
作者: Feis (永遠睡不著 @@)   2015-07-14 22:13:00
對阿. 我們只是在討論排序後的做法.另外一種就是 HashtableFYI: https://gist.github.com/feis/5fb3d820161a365add5a
作者: bben900911 (Ben)   2015-07-15 01:15:00
除非追求超過O(nlogn) 不然假設排序過還滿OK的吧?
作者: cobrasgo (人魚線變成鮪魚線,超帥)   2015-07-16 14:03:00
未排序的話那排序時間複雜度就是bottle neck了吧用空間換時間的話,這題有O(n)的解法啊我笨了,就是原po的寫法囧
作者: coal511464 (我一個人)   2015-07-18 09:31:00
面試白板題能答成這樣 那挺強的。
作者: EdisonX (卡卡獸)   2015-07-18 12:09:00
白板題...好熟的面試方式... @@

Links booklink

Contact Us: admin [ a t ] ucptt.com