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