logo
Redian新闻
>未名空间
>bagua - 娱乐八卦
>
著名武打演员计春华因病去世，他的哪部作品曾让你印象深刻？
avatar
著名武打演员计春华因病去世，他的哪部作品曾让你印象深刻？# bagua - 娱乐八卦
l*y
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上的讨论不清楚。谢谢。
avatar
f*n
2 楼
You will be charged an annual membership fee of $65.00 on August 1st, 2011.
The Annual Membership Fee is associated with the Card product and the
Benefits and Services offered on that Card. Also, a renewal membership fee
is charged to carry forward your membership with us. It is charged from
every Cardmember who has this Card.
I am sorry, we are unable to waive this fee from the account.
avatar
b*e
3 楼
一个好演员，演了一辈子的坏人
中国金牌反派明星，小时候的童年阴影，天龙八部、少林寺……
最近看猎毒人还看到他了，依旧气场很强，没想到今天已经去世了。
1方丈你不记得我了？我是马宁儿啊！！！
2印象最深的，是连城诀里的 血刀老祖，形神兼备，入木三分，成功还原了原著中的角
色，比男女主角更加令人印象深刻。资深原著党表示这就是小说里走出来的血刀老祖。
血刀抹头的招牌动作:
3谢霆锋版《浣花洗剑录》里计春华老师出演的白三空
4胡军版的天龙八部。 今天也就是11号下午四点半多的时候刚刚看完四十集的天龙八部
。 里面恶贯满盈段延庆，四大恶人之首。 还记忆犹新。小时候看他的秃鹰还有其他，
只有恐怖 害怕 畏惧。 一出现他的片段， 都会断电电视， 等五六分钟再开。 确定
没有了， 再看。站在再重温他的电视剧， 只有感叹，演技的精髓。 还有演坏人 演
恶人，也要演的光明磊落。
5《少林寺传奇》
看过他演的少林寺传奇1至3部，王仁则和高大人都演得入木三分！可惜啊，高大人，再
也不能保护背在他身上的那个盒子了。从
6《功夫小子闯情关》的碟片
计春华老师在这部片里也有出演，饰演的是一个没几句台词的打手，他的光头配上极具
特色的铁头功，当真称得上是那部电影里最有特点的角色了，虽然没台词。http://www.mitbbs.com/pic_home/weiyan/pic/Z/zhongjiezhe/25415/6.jpg
7《猎毒人》
计过身后事，
春盛知秋实，
华鼎送君去。
犹等故人归。
avatar
r*o
4 楼
我只想出了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上的讨论不清楚。谢谢。
avatar
h*e
5 楼
When I was calling to cancel my SPG card, I was offered $25 credit to keep
it, I said hell no.
avatar
l*y
6 楼
谢谢.比我的好很多了.

【在 r****o 的大作中提到】
: 我只想出了O(n^2)的解法。
: 先排序，然后对每个元素a[i]，找sum等于T-a[i]的pair。
:
: up
avatar
j*1
7 楼
zao jiu guan le
avatar
r*o
8 楼
想了一下，好像可以达到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
avatar
g*n
9 楼
还在犹豫是继续这个卡还是转成别的。。。
avatar
l*y
10 楼
这个...可能不对...
找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)。
: 希望大家对我的想法多提意见。
avatar
r*i
11 楼
65刀而已。。
avatar
o*r
12 楼
如果一开始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)。
: 希望大家对我的想法多提意见。
avatar
m*0
13 楼
犹豫了n次，舍不得关
avatar
r*o
14 楼
你们说的很对，我想的简单了些。不过我的方法可以排除掉一些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]，
avatar
S*a
15 楼
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上的讨论不清楚。谢谢。
avatar
r*o
16 楼
多谢，竟然还用到了fft。
在 Stigmata (Stigmata) 的大作中提到: 】
avatar
K*g
17 楼
不明白，你这个算法怎么会是O（n^2)呢，明明就是O（n*nlgn)

【在 r****o 的大作中提到】
: 我只想出了O(n^2)的解法。
: 先排序，然后对每个元素a[i]，找sum等于T-a[i]的pair。
:
: up
avatar
r*o
18 楼
找sum等于给定值的pair，复杂度O(n)，不是O(nlgn)

【在 K******g 的大作中提到】
: 不明白，你这个算法怎么会是O（n^2)呢，明明就是O（n*nlgn)
avatar
x*r
19 楼
你在找pair的时候是要用到hash map是吧？
我觉得O(NlgN）好难啊。

【在 r****o 的大作中提到】
: 找sum等于给定值的pair，复杂度O(n)，不是O(nlgn)
avatar
r*o
20 楼
用hash map可以，也可以两指针一前一后移动。

【在 x****r 的大作中提到】
: 你在找pair的时候是要用到hash map是吧？
: 我觉得O(NlgN）好难啊。
avatar
a*9
21 楼
不用吧 用两个指针一个在最前一个在最后
如果a[0]+a[n-1]>Sum, 就扔掉a[n-1]并把后指针前移,如果小就扔掉a[0]把前指针后移，
扫一遍就ok？

【在 x****r 的大作中提到】
: 你在找pair的时候是要用到hash map是吧？
: 我觉得O(NlgN）好难啊。
avatar
x*r
22 楼
哦对！排序好了可以这样
不过扫的时候找到了还得判断一下两个指针都不能指向之前选的i

【在 r****o 的大作中提到】
: 用hash map可以，也可以两指针一前一后移动。
avatar
x*r
23 楼
这个有时候会跳过正确解
假设数组是
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？
avatar
a*9
24 楼
我写的是错的，不好意思阿

【在 r****o 的大作中提到】
: 用hash map可以，也可以两指针一前一后移动。
avatar
a*9
25 楼
还有，找那个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选小了
avatar
x*r
26 楼
反正我觉得你的思路是很有道理的，不过因为数组不连续，所以实行起来很复杂，可能
需要在这种可能
跳过的情况下还是搜索两边，，这样可能就退化成O(N^2)了， 也有可能有更巧妙的方
法可以在nlgn找
到吧。

【在 a***9 的大作中提到】
: 还有，找那个pair是不包括当前取定的a[mid]剩下的数组中找的
avatar
e*6
27 楼
有一个解不知道对不对。。。
首先排序
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)
avatar
r*o
28 楼
这个想法不错，不过好像也不对。
举个例子，
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)
avatar
r*o
29 楼
好像很有道理阿，呵呵。
不过这段话我没看明白，能不能解释一下:
” 如果组后找到的pair是a[mid-1],a[mid+1],那么就看a[mid-1]+a[mid+1]，
若大了，那么说明有解的话，一定有一个数是落在mid左边(trivial)，所以
判左，否则判右。“

【在 a***9 的大作中提到】
: 还有，找那个pair是不包括当前取定的a[mid]剩下的数组中找的
avatar
r*o
30 楼
很NB啊，呵呵。感觉你说的是对的。

【在 a***9 的大作中提到】
: 还有，找那个pair是不包括当前取定的a[mid]剩下的数组中找的
avatar
x*r
31 楼
这个看起来挺对的呀，，求大牛出来给个定论哈。。

【在 a***9 的大作中提到】
: 还有，找那个pair是不包括当前取定的a[mid]剩下的数组中找的
avatar
K*g
32 楼
没有看懂，能否给个例子？

【在 a***9 的大作中提到】
: 还有，找那个pair是不包括当前取定的a[mid]剩下的数组中找的
avatar
l*y
33 楼
amoi9 你是不是删除了自己的一个帖子呀?
没看懂你的回复.

【在 a***9 的大作中提到】
: 还有，找那个pair是不包括当前取定的a[mid]剩下的数组中找的
avatar
K*g
34 楼
你找到了a[mid],在剩下的数组中没有找到sum等于T-a[mid]的pair，然后怎么做呢？

【在 a***9 的大作中提到】
: 还有，找那个pair是不包括当前取定的a[mid]剩下的数组中找的
avatar
K*g
36 楼
我知道那个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/
avatar
l*t
37 楼
这样的j,k组合个数是O(n*n)了吧.

【在 a***9 的大作中提到】
: 还有，找那个pair是不包括当前取定的a[mid]剩下的数组中找的
avatar
g*u
38 楼
3-sum is O(n^2) hard....
avatar
a*9
39 楼
发现了。。所以在想逻辑上有什么错。。

【在 g*****u 的大作中提到】
: 3-sum is O(n^2) hard....
avatar
r*o
40 楼
抱什么歉阿，我觉得你的想法即使错了，也是很NB的。呵呵。
能不能举个两个指针不连续的例子呢 (不是刚好隔着mid的那种情形把, 呵呵。

【在 a***9 的大作中提到】
: 发现了。。所以在想逻辑上有什么错。。
avatar
r*o
41 楼
我没想出反例出来...
谁能给个两个指针不连续又不隔着mid，或者两个指针不连续，隔着mid但不紧挨着mid
的例子?

【在 a***9 的大作中提到】
: 发现了。。所以在想逻辑上有什么错。。
avatar
a*9
42 楼
啊。。好像也不是。。我也不知道了。。帖子已经删了。。
也没办法让高人指出哪里逻辑出错了。。

mid

【在 r****o 的大作中提到】
: 我没想出反例出来...
: 谁能给个两个指针不连续又不隔着mid，或者两个指针不连续，隔着mid但不紧挨着mid
: 的例子?
avatar
a*9
43 楼
这个做法是错的～
发信人: amoi9 (amoi), 信区: JobHunting
标 题: Re: 问一道google面试题(from careercup)
发信站: BBS 未名空间站 (Sun Apr 11 22:34:54 2010, 美东)
Thanks for back up..
avatar
x*3
44 楼
a[mid]是指要找的那三个数里的中数吗

【在 a***9 的大作中提到】
: 这个做法是错的～
: 发信人: amoi9 (amoi), 信区: JobHunting
: 标 题: Re: 问一道google面试题(from careercup)
: 发信站: BBS 未名空间站 (Sun Apr 11 22:34:54 2010, 美东)
: Thanks for back up..
avatar
a*9
45 楼
这个做法是错的，它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..
avatar
r*o
46 楼
明白了，呵呵。多谢。

【在 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，而不是在第二
avatar
a*9
47 楼
avatar
o*r
48 楼
我说一个思路。
不过不是nlgn啊，应该还是N^2
1.sort, nlgn
2. assume a<=b<=c, a+b+c = sum;
这样 a<= sum/3;
c>= sum/3;
avatar
o*r
49 楼
还有我想指出的是，每次搜索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;
相关阅读
偶见川普周迅离婚了 (转载)乐华麦锐腾讯发布联合声明：三人将回归火箭少女腾讯要跟火箭101女团刚到底呀！刘亦菲干爹找的二菲，其实能说是高配版本刘嘉玲当年到底是被谁绑架的？知名公益人雷闯涉性侵：莫借公益身份行不轨之事郑爽可以说是我最喜欢的女明星了大奸似忠大伪似真，痞子冯小刚，拍点情怀电影就自以为是刘晓庆最近参加颁奖礼，这张脸也太僵了...郑爽与胡彦斌疑似复合？看完这个你还这样认为吗？你觉得那个地方的方言，是你最喜欢的？大牌明星的素颜照，看看谁的素颜更美？否认与郑爽复合后 胡彦斌被曝出新女友是王莫涵那些被劈腿的女明星们都还好吗？“凤凰传奇”原来还有另一层的关系，难怪感情那么好当于正弃“于妈色”后，《延禧攻略》能否与《如懿传》一战？被摸大腿和喝酒没关系你知道吗？它是国内唯一没有开通地铁的省会朱雨辰他妈曾经看上过霍思燕，但霍思燕的回答绝了！
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。