l*********y
发帖数: 142 | 1 given an array of n elements, find if there is a subset of 3 elements sum up
to value T with time complexity O(nlgn).
感觉这道题定义很清晰，但是只能想出O(n^2*lgn) 的brute force解法.
careercup上的讨论不清楚。谢谢。 |
r****o
发帖数: 1950 | 2 我只想出了O(n^2)的解法。
先排序，然后对每个元素a[i]，找sum等于T-a[i]的pair。
up
【在 l*********y 的大作中提到】
: given an array of n elements, find if there is a subset of 3 elements sum up
: to value T with time complexity O(nlgn).
: 感觉这道题定义很清晰，但是只能想出O(n^2*lgn) 的brute force解法.
: careercup上的讨论不清楚。谢谢。
|
l*********y
发帖数: 142 | 3 谢谢.比我的好很多了.
【在 r****o 的大作中提到】
: 我只想出了O(n^2)的解法。
: 先排序，然后对每个元素a[i]，找sum等于T-a[i]的pair。
:
: up
|
r****o
发帖数: 1950 | 4 想了一下，好像可以达到O(nlgn). 假定数组为 a[1]...a[n]。
先排序 O(nlgn)
然后用binary search 找a[i]，过程如下：
对于a[mid],如果a[n]+a[n-1]也比T-a[mid]小，说明a[mid]选值过小，故在右半边继续找a[mid]；如果a[1]+a[2]也比T-a[mid]大，说明a[mid]选值过大，则应在左半边继续找a[mid]，
继续该binary search，一直找到a[mid]，使得a[1]+a[2]<=T-a[mid]<=a[n-1]+a[n]，
然后可以线性查找出i,j，使得a[i]+a[j]=T-a[mid]。
binary search共需O(lgn)步。线性查找O(n)。
总复杂度还是O(nlgn)。
希望大家对我的想法多提意见。
【在 r****o 的大作中提到】
: 我只想出了O(n^2)的解法。
: 先排序，然后对每个元素a[i]，找sum等于T-a[i]的pair。
:
: up
|
l*********y
发帖数: 142 | 5 这个...可能不对...
找a[mid]只要a[1], a[2], a[n-1] and a[n]的info? 数组排序后会有multiple
solutions 符合你的条件 a[1]+a[2]<=T-a[mid]<=a[n-1]+a[n] 吧.
每个都linear search还是n^2呀.
还是非常感谢.
n]，
【在 r****o 的大作中提到】
: 想了一下，好像可以达到O(nlgn). 假定数组为 a[1]...a[n]。
: 先排序 O(nlgn)
: 然后用binary search 找a[i]，过程如下：
: 对于a[mid],如果a[n]+a[n-1]也比T-a[mid]小，说明a[mid]选值过小，故在右半边继续找a[mid]；如果a[1]+a[2]也比T-a[mid]大，说明a[mid]选值过大，则应在左半边继续找a[mid]，
: 继续该binary search，一直找到a[mid]，使得a[1]+a[2]<=T-a[mid]<=a[n-1]+a[n]，
: 然后可以线性查找出i,j，使得a[i]+a[j]=T-a[mid]。
: binary search共需O(lgn)步。线性查找O(n)。
: 总复杂度还是O(nlgn)。
: 希望大家对我的想法多提意见。
|
o********r
发帖数: 79 | 6 如果一开始mid就满足a[1]+a[2]<=T-a[mid]<=a[n-1]+a[n]，
范围不能缩小到1/2啊。
这个条件太松了，只是满足这个，不能说明a[mid]就是要找的三个数中的一个。
边继续找a[mid]；
如果a[1]+a[2]也比T-a[mid]大，说明a[mid]选值过大，则应在左半边继续找a[mid]，
n]，
【在 r****o 的大作中提到】
: 想了一下，好像可以达到O(nlgn). 假定数组为 a[1]...a[n]。
: 先排序 O(nlgn)
: 然后用binary search 找a[i]，过程如下：
: 对于a[mid],如果a[n]+a[n-1]也比T-a[mid]小，说明a[mid]选值过小，故在右半边继续找a[mid]；如果a[1]+a[2]也比T-a[mid]大，说明a[mid]选值过大，则应在左半边继续找a[mid]，
: 继续该binary search，一直找到a[mid]，使得a[1]+a[2]<=T-a[mid]<=a[n-1]+a[n]，
: 然后可以线性查找出i,j，使得a[i]+a[j]=T-a[mid]。
: binary search共需O(lgn)步。线性查找O(n)。
: 总复杂度还是O(nlgn)。
: 希望大家对我的想法多提意见。
|
r****o
发帖数: 1950 | 7 你们说的很对，我想的简单了些。不过我的方法可以排除掉一些a[i]。呵呵。
【在 o********r 的大作中提到】
: 如果一开始mid就满足a[1]+a[2]<=T-a[mid]<=a[n-1]+a[n]，
: 范围不能缩小到1/2啊。
: 这个条件太松了，只是满足这个，不能说明a[mid]就是要找的三个数中的一个。
:
: 边继续找a[mid]；
: 如果a[1]+a[2]也比T-a[mid]大，说明a[mid]选值过大，则应在左半边继续找a[mid]，
: n]，
|
S******a
发帖数: 862 | 8 http://en.wikipedia.org/wiki/3SUM
sum up
【在 l*********y 的大作中提到】
: given an array of n elements, find if there is a subset of 3 elements sum up
: to value T with time complexity O(nlgn).
: 感觉这道题定义很清晰，但是只能想出O(n^2*lgn) 的brute force解法.
: careercup上的讨论不清楚。谢谢。
|
r****o
发帖数: 1950 | 9 多谢，竟然还用到了fft。
在 Stigmata (Stigmata) 的大作中提到: 】 |
K******g
发帖数: 1870 | 10 不明白，你这个算法怎么会是O（n^2)呢，明明就是O（n*nlgn)
【在 r****o 的大作中提到】
: 我只想出了O(n^2)的解法。
: 先排序，然后对每个元素a[i]，找sum等于T-a[i]的pair。
:
: up
|
|
|
r****o
发帖数: 1950 | 11 找sum等于给定值的pair，复杂度O(n)，不是O(nlgn)
【在 K******g 的大作中提到】
: 不明白，你这个算法怎么会是O（n^2)呢，明明就是O（n*nlgn)
|
x****r
发帖数: 99 | 12 你在找pair的时候是要用到hash map是吧？
我觉得O(NlgN）好难啊。
【在 r****o 的大作中提到】
: 找sum等于给定值的pair，复杂度O(n)，不是O(nlgn)
|
r****o
发帖数: 1950 | 13 用hash map可以，也可以两指针一前一后移动。
【在 x****r 的大作中提到】
: 你在找pair的时候是要用到hash map是吧？
: 我觉得O(NlgN）好难啊。
|
a***9
发帖数: 364 | 14 不用吧 用两个指针一个在最前一个在最后
如果a[0]+a[n-1]>Sum, 就扔掉a[n-1]并把后指针前移,如果小就扔掉a[0]把前指针后移，
扫一遍就ok？
【在 x****r 的大作中提到】
: 你在找pair的时候是要用到hash map是吧？
: 我觉得O(NlgN）好难啊。
|
x****r
发帖数: 99 | 15 哦对！排序好了可以这样
不过扫的时候找到了还得判断一下两个指针都不能指向之前选的i
【在 r****o 的大作中提到】
: 用hash map可以，也可以两指针一前一后移动。
|
x****r
发帖数: 99 | 16 这个有时候会跳过正确解
假设数组是
1，2，100，200，600，601，1000
要找和为701的，有解事（1 + 100 + 600）
1.
现在一开始选a[mid] = 200, 要找和为 501的pair，最后指针式指向100和200
这样你的解法中会判断mid选小了，
2.
选择右侧中间的601， 要找和为100的pair，最后指针指向1， 2
这样还会判断mid选小了
**这样下次就会去指向arr[mid] = 1000, 把在左侧的正确解 600 跳过了
这样的跳过正确解的情况可能发生在任何地方，原因是数组不连续，
所以找pair的时候会误判mid左了还是右了
如果不对请指正，谢谢：P
mid
【在 a***9 的大作中提到】
: 不用吧 用两个指针一个在最前一个在最后
: 如果a[0]+a[n-1]>Sum, 就扔掉a[n-1]并把后指针前移,如果小就扔掉a[0]把前指针后移，
: 扫一遍就ok？
|
a***9
发帖数: 364 | 17 我写的是错的，不好意思阿
【在 r****o 的大作中提到】
: 用hash map可以，也可以两指针一前一后移动。
|
a***9
发帖数: 364 | 18 还有，找那个pair是不包括当前取定的a[mid]剩下的数组中找的
【在 x****r 的大作中提到】
: 这个有时候会跳过正确解
: 假设数组是
: 1，2，100，200，600，601，1000
: 要找和为701的，有解事（1 + 100 + 600）
: 1.
: 现在一开始选a[mid] = 200, 要找和为 501的pair，最后指针式指向100和200
: 这样你的解法中会判断mid选小了，
: 2.
: 选择右侧中间的601， 要找和为100的pair，最后指针指向1， 2
: 这样还会判断mid选小了
|
x****r
发帖数: 99 | 19 反正我觉得你的思路是很有道理的，不过因为数组不连续，所以实行起来很复杂，可能
需要在这种可能
跳过的情况下还是搜索两边，，这样可能就退化成O(N^2)了， 也有可能有更巧妙的方
法可以在nlgn找
到吧。
【在 a***9 的大作中提到】
: 还有，找那个pair是不包括当前取定的a[mid]剩下的数组中找的
|
e**********6
发帖数: 78 | 20 有一个解不知道对不对。。。
首先排序
i=0,j=length of array;
x=sum-array[i]-array[j]
find x between i and j using binary search
然后如果第一次二分查找判断出array[middle=(i+j)/2]比x小，且没找到x，下一次就i
++（因为需要更大的值）；反之则j--。
重复以上步骤。
排序nlogn，从i++或者j--遍历是n，然后每次遍历会进行二分查找为logn。结果就是O(
nlogn) |
|
|
r****o
发帖数: 1950 | 21 这个想法不错，不过好像也不对。
举个例子，
a[]=1,9.50,60,65,70,101，找3个数sum=160,有解为9+50+101=160。
按你的解法，先binary search 58 (160-1-101=58),没找到，发现a[mid]=60>58，j--,
这样就把101给丢了。
就i
O(
【在 e**********6 的大作中提到】
: 有一个解不知道对不对。。。
: 首先排序
: i=0,j=length of array;
: x=sum-array[i]-array[j]
: find x between i and j using binary search
: 然后如果第一次二分查找判断出array[middle=(i+j)/2]比x小，且没找到x，下一次就i
: ++（因为需要更大的值）；反之则j--。
: 重复以上步骤。
: 排序nlogn，从i++或者j--遍历是n，然后每次遍历会进行二分查找为logn。结果就是O(
: nlogn)
|
r****o
发帖数: 1950 | 22 好像很有道理阿，呵呵。
不过这段话我没看明白，能不能解释一下:
” 如果组后找到的pair是a[mid-1],a[mid+1],那么就看a[mid-1]+a[mid+1]，
若大了，那么说明有解的话，一定有一个数是落在mid左边(trivial)，所以
判左，否则判右。“
【在 a***9 的大作中提到】
: 还有，找那个pair是不包括当前取定的a[mid]剩下的数组中找的
|
r****o
发帖数: 1950 | 23 很NB啊，呵呵。感觉你说的是对的。
【在 a***9 的大作中提到】
: 还有，找那个pair是不包括当前取定的a[mid]剩下的数组中找的
|
x****r
发帖数: 99 | 24 这个看起来挺对的呀，，求大牛出来给个定论哈。。
【在 a***9 的大作中提到】
: 还有，找那个pair是不包括当前取定的a[mid]剩下的数组中找的
|
K******g
发帖数: 1870 | 25 没有看懂，能否给个例子？
【在 a***9 的大作中提到】
: 还有，找那个pair是不包括当前取定的a[mid]剩下的数组中找的
|
l*********y
发帖数: 142 | 26 amoi9 你是不是删除了自己的一个帖子呀?
没看懂你的回复.
【在 a***9 的大作中提到】
: 还有，找那个pair是不包括当前取定的a[mid]剩下的数组中找的
|
K******g
发帖数: 1870 | 27 你找到了a[mid],在剩下的数组中没有找到sum等于T-a[mid]的pair，然后怎么做呢？
【在 a***9 的大作中提到】
: 还有，找那个pair是不包括当前取定的a[mid]剩下的数组中找的
|
l*********y
发帖数: 142 | 28 OK.这回懂了。非常感谢amoi9,确实很牛。
洱东金茗，建议你看一下
http://cstechie.com/find-2-elements-in-a-sorted-array-with-a-given-sum-java-source-code/
【在 a***9 的大作中提到】
: 还有，找那个pair是不包括当前取定的a[mid]剩下的数组中找的
|
K******g
发帖数: 1870 | 29 我知道那个O（n)的找sum=T的pair的方法，我是问怎么用二分法确定第一个数。
给个数组，我先查a[mid]，然后在剩下的n-1个数中找pair，如果没有找到，怎么确定
下一个a[mid]?
【在 l*********y 的大作中提到】
: OK.这回懂了。非常感谢amoi9,确实很牛。
: 洱东金茗，建议你看一下
: http://cstechie.com/find-2-elements-in-a-sorted-array-with-a-given-sum-java-source-code/
|
l*******t
发帖数: 642 | 30 这样的j,k组合个数是O(n*n)了吧.
【在 a***9 的大作中提到】
: 还有，找那个pair是不包括当前取定的a[mid]剩下的数组中找的
|
|
|
g*****u
发帖数: 298 | 31 3-sum is O(n^2) hard.... |
a***9
发帖数: 364 | 32 发现了。。所以在想逻辑上有什么错。。
【在 g*****u 的大作中提到】
: 3-sum is O(n^2) hard....
|
r****o
发帖数: 1950 | 33 抱什么歉阿，我觉得你的想法即使错了，也是很NB的。呵呵。
能不能举个两个指针不连续的例子呢 (不是刚好隔着mid的那种情形把, 呵呵。
【在 a***9 的大作中提到】
: 发现了。。所以在想逻辑上有什么错。。
|
r****o
发帖数: 1950 | 34 我没想出反例出来...
谁能给个两个指针不连续又不隔着mid，或者两个指针不连续，隔着mid但不紧挨着mid
的例子?
【在 a***9 的大作中提到】
: 发现了。。所以在想逻辑上有什么错。。
|
a***9
发帖数: 364 | 35 啊。。好像也不是。。我也不知道了。。帖子已经删了。。
也没办法让高人指出哪里逻辑出错了。。
mid
【在 r****o 的大作中提到】
: 我没想出反例出来...
: 谁能给个两个指针不连续又不隔着mid，或者两个指针不连续，隔着mid但不紧挨着mid
: 的例子?
|
a***9
发帖数: 364 | 36 这个做法是错的～
发信人: amoi9 (amoi), 信区: JobHunting
标 题: Re: 问一道google面试题(from careercup)
发信站: BBS 未名空间站 (Sun Apr 11 22:34:54 2010, 美东)
Thanks for back up.. |
x******3
发帖数: 245 | 37 a[mid]是指要找的那三个数里的中数吗
【在 a***9 的大作中提到】
: 这个做法是错的～
: 发信人: amoi9 (amoi), 信区: JobHunting
: 标 题: Re: 问一道google面试题(from careercup)
: 发信站: BBS 未名空间站 (Sun Apr 11 22:34:54 2010, 美东)
: Thanks for back up..
|
a***9
发帖数: 364 | 38 这个做法是错的，它sound但不complete.
虽然每次判左判右的逻辑没有错，但是判左判右的同时认为在一半的子区间
内就是它的不对了。
比如这个例子：
1，6，8，10，12，15，18，23，26，30，50
找三个数和=25，有解： 1+6+18
但根据我们的算法，
第一步到15，指标最后落在6和8，这时候往左找没错；
第二步到8，指标落在6和10，是mid-1和mid+1的情况，而6+10<25-8,所以往
右找没错，但注意，这个时候8的右边解中必须包含的数是18，而不是在第二
步的子区间[10,12]中；
第三步，到10，指标落在6和8，函数返回无解，which is wrong..
【在 a***9 的大作中提到】
: 这个做法是错的～
: 发信人: amoi9 (amoi), 信区: JobHunting
: 标 题: Re: 问一道google面试题(from careercup)
: 发信站: BBS 未名空间站 (Sun Apr 11 22:34:54 2010, 美东)
: Thanks for back up..
|
r****o
发帖数: 1950 | 39 明白了，呵呵。多谢。
【在 a***9 的大作中提到】
: 这个做法是错的，它sound但不complete.
: 虽然每次判左判右的逻辑没有错，但是判左判右的同时认为在一半的子区间
: 内就是它的不对了。
: 比如这个例子：
: 1，6，8，10，12，15，18，23，26，30，50
: 找三个数和=25，有解： 1+6+18
: 但根据我们的算法，
: 第一步到15，指标最后落在6和8，这时候往左找没错；
: 第二步到8，指标落在6和10，是mid-1和mid+1的情况，而6+10<25-8,所以往
: 右找没错，但注意，这个时候8的右边解中必须包含的数是18，而不是在第二
|
a***9
发帖数: 364 | |
|
|
o********r
发帖数: 79 | 41 我说一个思路。
不过不是nlgn啊，应该还是N^2
1.sort, nlgn
2. assume a<=b<=c, a+b+c = sum;
这样 a<= sum/3;
c>= sum/3; |
o********r
发帖数: 79 | 42 还有我想指出的是，每次搜索a，只在[0,k]和[0,sum/3]的交集里找。
每次搜索c，只在[k,n-1]和[sum/3,n-1]的交集里找。
【在 o********r 的大作中提到】
: 我说一个思路。
: 不过不是nlgn啊，应该还是N^2
: 1.sort, nlgn
: 2. assume a<=b<=c, a+b+c = sum;
: 这样 a<= sum/3;
: c>= sum/3;
|
