P*******b
发帖数: 1001 | 1 数组找第二大的 n + logn - 2，不用额外空间的算法
那位高手给解释一下。好不？
thank you! |
s*****n
发帖数: 5488 | 2 赛马法把。
【在 P*******b 的大作中提到】
: 数组找第二大的 n + logn - 2，不用额外空间的算法
: 那位高手给解释一下。好不？
: thank you!
|
l******c
发帖数: 2555 | 3 no way without extra space
【在 P*******b 的大作中提到】
: 数组找第二大的 n + logn - 2，不用额外空间的算法
: 那位高手给解释一下。好不？
: thank you!
|
c*********t
发帖数: 32 | 4 tournament method.
这个算法复杂度(n+logn-2)应该是找出最大和第二大数的。
the largest: O(n-1)
the second largest: O(logn-1)
So it is O(n-1+logn-1)=O(n+logn-2).
以上只是解释了算法复杂度，至于额外空间，我觉得问得有点怪，还请其他人解释一下。
【在 P*******b 的大作中提到】
: 数组找第二大的 n + logn - 2，不用额外空间的算法
: 那位高手给解释一下。好不？
: thank you!
|
P*******b
发帖数: 1001 | 5 我咋觉得要额外空间呢？
【在 s*****n 的大作中提到】
: 赛马法把。
|
c*******t
发帖数: 1095 | 6 应该要的吧
因为要构建一个tree
当然如果不要额外空间早第i大的元素也可以在O(N)完成的 |
P*******b
发帖数: 1001 | 7 我记得我看到一个帖子说不需要额外空间。
忘了哪里看到的。
【在 c*******t 的大作中提到】
: 应该要的吧
: 因为要构建一个tree
: 当然如果不要额外空间早第i大的元素也可以在O(N)完成的
|
c*******t
发帖数: 1095 | 8 为什么第一次遍历整个数组的时候不找两个变量分别存最大的和第二大的？非得再比较
一次 |
n*****y
发帖数: 361 | 9 worst case will be 2n-2.
【在 c*******t 的大作中提到】
: 为什么第一次遍历整个数组的时候不找两个变量分别存最大的和第二大的？非得再比较
: 一次
|
P*******b
发帖数: 1001 | 10 那位高手再给指点指点啊
【在 P*******b 的大作中提到】
: 数组找第二大的 n + logn - 2，不用额外空间的算法
: 那位高手给解释一下。好不？
: thank you!
|
P********l
发帖数: 452 | 11 来给证明一下你要的东西不存在。
不需要额外空间意味着与当前状态无关。否则你得找地方放状态才行。
你说第二大的数只需要o(ln),如果我拿取一个最大的数拼凑到这个数组里，那么原来的
第一大也可以在o(ln)完成。你知道我想说什么了。
【在 P*******b 的大作中提到】
: 我记得我看到一个帖子说不需要额外空间。
: 忘了哪里看到的。
|
P*******b
发帖数: 1001 | 12 我也不知道啊。你看前面牛人的总结，说是不需要额外的空间。
下面这个链接的题目四
http://www.mitbbs.com/article_t/JobHunting/31502251.html
【在 P********l 的大作中提到】
: 来给证明一下你要的东西不存在。
: 不需要额外空间意味着与当前状态无关。否则你得找地方放状态才行。
: 你说第二大的数只需要o(ln),如果我拿取一个最大的数拼凑到这个数组里，那么原来的
: 第一大也可以在o(ln)完成。你知道我想说什么了。
|
