h****8
发帖数: 599 | 1 Ｎ个数的数组，找出最大和第二大的数，只能用Ｎ＋ＬｏｇＮ－２的比较次数，不用额
外空间 |
s*********t
发帖数: 1663 | 2 不会。。顶
【在 h****8 的大作中提到】
: Ｎ个数的数组，找出最大和第二大的数，只能用Ｎ＋ＬｏｇＮ－２的比较次数，不用额
: 外空间
|
y*c
发帖数: 904 | 3 This is a homework problem in CLRS.
Tournament. |
l******c
发帖数: 2555 | 4 不用额外空间??? no solution
【在 h****8 的大作中提到】
: Ｎ个数的数组，找出最大和第二大的数，只能用Ｎ＋ＬｏｇＮ－２的比较次数，不用额
: 外空间
|
h****8
发帖数: 599 | 5 那先说说如果可以用额外空间怎么做吧
【在 l******c 的大作中提到】
: 不用额外空间??? no solution
|
d**e
发帖数: 6098 | 6 能不能devide and conquer?
不过好像又差一点点。如果n = 8，则要求最多用 (8 + log 8 - 2 = 9)
但实际上又差一点，要用到 10个比较
【在 h****8 的大作中提到】
: 那先说说如果可以用额外空间怎么做吧
|
h****8
发帖数: 599 | 7 展开说说
【在 d**e 的大作中提到】
: 能不能devide and conquer?
: 不过好像又差一点点。如果n = 8，则要求最多用 (8 + log 8 - 2 = 9)
: 但实际上又差一点，要用到 10个比较
|
z****e
发帖数: 2024 | 8 use a min-heap which size is 2.
【在 h****8 的大作中提到】
: 那先说说如果可以用额外空间怎么做吧
|
l*****a
发帖数: 14598 | 9 this is a common way
but u still need to compare more than n+logn-2 times
【在 z****e 的大作中提到】
: use a min-heap which size is 2.
|
a***9
发帖数: 364 | 10 可以用的话，从底往上建二叉树，每两个数比较，大的胜出上升为parent；
这样经N-1次比较得到最大数，第二大的数，只需要把跟最大数比过的数比
一遍就出来了,logN-1次
【在 h****8 的大作中提到】
: 那先说说如果可以用额外空间怎么做吧
|
|
|
y*c
发帖数: 904 | 11
This one should be correct.
【在 a***9 的大作中提到】
: 可以用的话，从底往上建二叉树，每两个数比较，大的胜出上升为parent；
: 这样经N-1次比较得到最大数，第二大的数，只需要把跟最大数比过的数比
: 一遍就出来了,logN-1次
|
l******c
发帖数: 2555 | 12 logN extra space
【在 y*c 的大作中提到】
:
: This one should be correct.
|
l******c
发帖数: 2555 | 13 logN extra space
【在 y*c 的大作中提到】
:
: This one should be correct.
|
d**e
发帖数: 6098 | 14 认真算了一下，差了不是一点点，呵呵。
和前面amoi9说的差不多，也是二叉树，但不记录和谁比较过
不过节点返回的是子树里的最大和第二大 pair(max, 2nd_max)
在左右子树都是树叶时，由于只有两个数，就比较一次谁大谁小就行了
其它的节点，则可能是三个或四个数比较，这里要比较两次
最后比较次数是 N/2 + (N - 1 - N/2) * 2 = N + N/2 - 2
差远了…… :(
【在 h****8 的大作中提到】
: 展开说说
|
s********a
发帖数: 1447 | 15 CLRS到底是那本书啊？ 3X~
//我都问了好几遍了:(
【在 y*c 的大作中提到】
: This is a homework problem in CLRS.
: Tournament.
|
A*****n
发帖数: 243 | 16 Introduction to Algorithms
http://en.wikipedia.org/wiki/Introduction_to_Algorithms
【在 s********a 的大作中提到】
: CLRS到底是那本书啊？ 3X~
: //我都问了好几遍了:(
|
c*********n
发帖数: 1057 | 17 知道啥是google么？
【在 s********a 的大作中提到】
: CLRS到底是那本书啊？ 3X~
: //我都问了好几遍了:(
|
l*******e
发帖数: 309 | 18 inplace sort算不算不要extra空间？ |
h****8
发帖数: 599 | 19 算它不需要额外空间好了
【在 l*******e 的大作中提到】
: inplace sort算不算不要extra空间？
|
y**i
发帖数: 1112 | 20 这个是标准答案，不过需要额外2N-1个空间吧
【在 a***9 的大作中提到】
: 可以用的话，从底往上建二叉树，每两个数比较，大的胜出上升为parent；
: 这样经N-1次比较得到最大数，第二大的数，只需要把跟最大数比过的数比
: 一遍就出来了,logN-1次
|
|
|
l*******e
发帖数: 309 | 21 能不能把路径给encode起来， 等最大数找出来以后，把路径decode出来，从array里面
找出被最大数打败的数？ |
s********a
发帖数: 1447 | |
s********a
发帖数: 1447 | 23 不知道~
【在 c*********n 的大作中提到】
: 知道啥是google么？
|
l*****a
发帖数: 14598 | 24 could u tell this to the interviewer?
【在 s********a 的大作中提到】
: 不知道~
|
s********a
发帖数: 1447 | 25 sure~
【在 l*****a 的大作中提到】
: could u tell this to the interviewer?
|
l*******e
发帖数: 309 | 26 想了个解法需要N-1个交换，N+logN-2个比较，O((logN)^2)个bit的空间, 大虾看看对
不对？
二叉树深度优先比较，把大的交换到左边，同时记录是否交换过。最后最大的在最左边
，同时有最大的交换记录。可以回溯到原来最大数的位置。再根据最大数的位置和交换
记录，可以把跟最大数交换过的数找出来。在这里面找第二大的数。 |
m*****g
发帖数: 226 | 27 真能用二茶树结构的话，先把array看成一个balanced binary tree
然后 left child 和 right child 比，大的变成left child
然后left child 跟 parent 比，大的变成parent
依次类推，最后 root变最大，比了n-1次，root的left child第二大 |
h****8
发帖数: 599 | 28 ｗｏｒｓｔ ｃａｓｅ，最大数已开始就在最左边，那你的交换记录就是空啦
【在 l*******e 的大作中提到】
: 想了个解法需要N-1个交换，N+logN-2个比较，O((logN)^2)个bit的空间, 大虾看看对
: 不对？
: 二叉树深度优先比较，把大的交换到左边，同时记录是否交换过。最后最大的在最左边
: ，同时有最大的交换记录。可以回溯到原来最大数的位置。再根据最大数的位置和交换
: 记录，可以把跟最大数交换过的数找出来。在这里面找第二大的数。
|
l*******e
发帖数: 309 | 29
if not swapped, record 0, otherwise record 1.
if all zeros, then check a[1], a[2], a[4], a[8] ...
【在 h****8 的大作中提到】
: ｗｏｒｓｔ ｃａｓｅ，最大数已开始就在最左边，那你的交换记录就是空啦
|
K******g
发帖数: 1870 | 30 请问你怎么coding呢？说倒是容易。
【在 a***9 的大作中提到】
: 可以用的话，从底往上建二叉树，每两个数比较，大的胜出上升为parent；
: 这样经N-1次比较得到最大数，第二大的数，只需要把跟最大数比过的数比
: 一遍就出来了,logN-1次
|
