今天晚上人好多 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>gardening - 拈花惹草

今天晚上人好多

今天晚上人好多# gardening - 拈花惹草

e*e2013-11-03 07:11

1 楼

在arraylist里面有乱序的数字,如何找出两个
数字使得和为0,using O(n), 然后如何找出三个数字和为0, using O(n^2), 四个数字
和为0, using O(n^2)的解,然后如何找出五个数字和为0, using O(n^3)的
解.
谢谢！

c*n2013-11-03 07:11

2 楼

fine print是说hotel room directly booked from hotel (as supposed to from
travel agency) 但是没有强调积分算不算

T*42013-11-03 07:11

3 楼

可以干点啥呢

r*y2013-11-03 07:11

4 楼

O(n) to sort the list firstly ?

【在 e***e 的大作中提到】

: 在arraylist里面有乱序的数字,如何找出两个
: 数字使得和为0,using O(n), 然后如何找出三个数字和为0, using O(n^2), 四个数字
: 和为0, using O(n^2)的解,然后如何找出五个数字和为0, using O(n^3)的
: 解.
: 谢谢！

l*i2013-11-03 07:11

5 楼

估计是不算的

【在 c*******n 的大作中提到】

: fine print是说hotel room directly booked from hotel (as supposed to from
: travel agency) 但是没有强调积分算不算

z*e2013-11-03 07:11

6 楼

看四姐奔？

【在 T*******4 的大作中提到】

: 可以干点啥呢

s*y2013-11-03 07:11

7 楼

http://www.mitbbs.com/article/JobHunting/31874123_3.html

【在 e***e 的大作中提到】

x*12013-11-03 07:11

8 楼

可以去二手版求一些，应该比自己直接买便宜

【在 c*******n 的大作中提到】

: fine print是说hotel room directly booked from hotel (as supposed to from
: travel agency) 但是没有强调积分算不算

T*42013-11-03 07:11

9 楼

我想看蓝星大厨MM

【在 z*****e 的大作中提到】

: 看四姐奔？

o*e2013-11-03 07:11

10 楼

对于5个的情形，可以分成2和3来解决。对于每一个特定的target, 3个元素的找法可
以O(n^2)得到。（通过先对原来的数组排序，再利用三个指针）
而对于两个元素的和，可以用 O(n^2)建立hashtable, 依次exhaust里面所有的元素ele
, 在3里面找对用的 target = 0 - ele
总时间是O(n^4)

s*c2013-11-03 07:11

11 楼

还能顺便关别人几张卡，哈哈

【在 x***1 的大作中提到】

: 可以去二手版求一些，应该比自己直接买便宜

s*y2013-11-03 07:11

12 楼

4 是 O(n^2)
那么为什么不可以把5切成1和4，那就是O（n^3)阿
then it wil

ele

【在 o******e 的大作中提到】

: 对于5个的情形，可以分成2和3来解决。对于每一个特定的target, 3个元素的找法可
: 以O(n^2)得到。（通过先对原来的数组排序，再利用三个指针）
: 而对于两个元素的和，可以用 O(n^2)建立hashtable, 依次exhaust里面所有的元素ele
: , 在3里面找对用的 target = 0 - ele
: 总时间是O(n^4)

f*s2013-11-03 07:11

13 楼

哈哈

【在 s**c 的大作中提到】

: 还能顺便关别人几张卡，哈哈

o*e2013-11-03 07:11

14 楼

对了，应该是这么做，谢谢！
我原先考虑过这么拆，竟然一时糊涂给否定掉了。:)

g*y2013-11-03 07:11

15 楼

为什么4个是O(n^2)？
按照那个解法，遍历pair就需要O(n^2), 然后的计算怎么能常数时间完成？

o*e2013-11-03 07:11

16 楼

可以用hashtable,这样查询时间仅为O(1)

g*y2013-11-03 07:11

17 楼

可以说说怎么建hashtable吗？
对于这个例子：{1, 1, -3, 100}

【在 o******e 的大作中提到】

: 可以用hashtable,这样查询时间仅为O(1)

o*e2013-11-03 07:11

18 楼

我想是用pair 作为元素建立hashtable 这样总的元素个数是~n^2

g*y2013-11-03 07:11

19 楼

你说的是hashset? 还是hashtable?
如果是hashset, 不能确定解；
如果是hashtable, 我的理解是value -> int,int的映射，否则没法查+/-value。要是
那样就是一对多的映射。当然你也可以value -> ArrayList来表示，那就不
能保证O(1)时间。
还是我理解有误？

【在 o******e 的大作中提到】

: 我想是用pair 作为元素建立hashtable 这样总的元素个数是~n^2

o*e2013-11-03 07:11

20 楼

嗯, 你是对的,同求正解.