e***e
发帖数: 168 | 1 在arraylist里面有乱序的数字,如何找出两个
数字使得和为0,using O(n), 然后如何找出三个数字和为0, using O(n^2), 四个数字
和为0, using O(n^2)的解,然后如何找出五个数字和为0, using O(n^3)的
解.
谢谢！ | r*******y
发帖数: 1081 | 2 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)的
: 解.
: 谢谢！
| s*****y
发帖数: 897 | 3 http://www.mitbbs.com/article/JobHunting/31874123_3.html
【在 e***e 的大作中提到】
: 在arraylist里面有乱序的数字,如何找出两个
: 数字使得和为0,using O(n), 然后如何找出三个数字和为0, using O(n^2), 四个数字
: 和为0, using O(n^2)的解,然后如何找出五个数字和为0, using O(n^3)的
: 解.
: 谢谢！
| o******e
发帖数: 74 | 4 对于5个的情形，可以分成2和3来解决。 对于每一个特定的target, 3个元素的找法可
以O(n^2)得到。（通过先对原来的数组排序，再利用 三个指针）
而对于两个元素的和，可以用 O(n^2)建立hashtable, 依次exhaust里面所有的元素ele
, 在3里面找对用的 target = 0 - ele
总时间是O(n^4) | s*****y
发帖数: 897 | 5 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)
| o******e
发帖数: 74 | 6 对了，应该是这么做，谢谢！
我原先考虑过这么拆，竟然一时糊涂给否定掉了。:) | g**********y
发帖数: 14569 | 7 为什么4个是O(n^2)？
按照那个解法，遍历pair就需要O(n^2), 然后的计算怎么能常数时间完成？ | o******e
发帖数: 74 | 8 可以用hashtable,这样查询时间仅为O(1) | g**********y
发帖数: 14569 | 9 可以说说怎么建hashtable吗？
对于这个例子：{1, 1, -3, 100}
【在 o******e 的大作中提到】
: 可以用hashtable,这样查询时间仅为O(1)
| o******e
发帖数: 74 | 10 我想是用pair 作为元素建立hashtable 这样总的元素个数是~n^2 | g**********y
发帖数: 14569 | 11 你说的是hashset? 还是hashtable?
如果是hashset, 不能确定解；
如果是hashtable, 我的理解是value -> int,int的映射，否则没法查+/-value。要是
那样就是一对多的映射。当然你也可以value -> ArrayList来表示，那就不
能保证O(1)时间。
还是我理解有误？
【在 o******e 的大作中提到】
: 我想是用pair 作为元素建立hashtable 这样总的元素个数是~n^2
| o******e
发帖数: 74 | |
|
