b*****b
发帖数: 181 | 1 1.given 一个compare(T a, T b). 返回true if a>b, 返回false if a
等的情况.
2. compare()是不transitive的, 比如说 a>b, b>c, 不能得到a>c. 有可能 c>a.
3. given 一个vector v.
求最快的找出v中的最大值.
我给了一个O(N^2). 但要求一个更快的. | t****o
发帖数: 33 | 2 有些不理解，如果a>b, b>c,无法有transitive property得到a>c,那么是不是意味着无
法对他们进行排序？ | J*****a
发帖数: 46 | 3 就当做平常的比较就可以了 这样找出来的最大的要么真的是最大的 要么有环 | p***y
发帖数: 637 | 4 如果大小不能传递，如何确定哪个是最大的啊？逻辑上有问题，比如我可以定义a>b, b
>c, c>a, 那谁最大呢？
【在 J*****a 的大作中提到】
: 就当做平常的比较就可以了 这样找出来的最大的要么真的是最大的 要么有环
| z*******g
发帖数: 103 | 5 感觉最大应该这么定义：有唯一一个数与他所有数compare以后都显示这个数比较大。
那么从左取第一个数开始，与第二个compare，直到某个数比他大（如果到最后，那就
他最大）。然后从比他大的那个数开始重复上述过程。
例子如下： a, b, c, d, e, f, g, h, i, j, k
假设 a比b,c,d大，比e小，那么排除a, b,c,d；最大数只能在剩下的数里。
这样就相当回到了问题开始，不过砍掉了a，b，c，d
看了应该是 O（n）吧 | I**********s
发帖数: 441 | 6 这个定义比较好: 有唯一一个数与他所有数compare以后都显示这个数比较大。
过程和find celebrity那个问题类似:
每次两个数比较, 比较小那个可以排除掉不是最大. 经过n-1次比较得到一个剩下的数,
再把这个数和其它n-1个数的每一个比较, 结果是要么这个数是最大要么最大不存在.
总共比较2(n-1)次, 是O(n).
【在 z*******g 的大作中提到】
: 感觉最大应该这么定义：有唯一一个数与他所有数compare以后都显示这个数比较大。
: 那么从左取第一个数开始，与第二个compare，直到某个数比他大（如果到最后，那就
: 他最大）。然后从比他大的那个数开始重复上述过程。
: 例子如下： a, b, c, d, e, f, g, h, i, j, k
: 假设 a比b,c,d大，比e小，那么排除a, b,c,d；最大数只能在剩下的数里。
: 这样就相当回到了问题开始，不过砍掉了a，b，c，d
: 看了应该是 O（n）吧
| z*******g
发帖数: 103 | 7 嗯，我倒是没有考虑不存在，如果一定存在且唯一，那扫一遍就好了
数,
.
【在 I**********s 的大作中提到】
: 这个定义比较好: 有唯一一个数与他所有数compare以后都显示这个数比较大。
: 过程和find celebrity那个问题类似:
: 每次两个数比较, 比较小那个可以排除掉不是最大. 经过n-1次比较得到一个剩下的数,
: 再把这个数和其它n-1个数的每一个比较, 结果是要么这个数是最大要么最大不存在.
: 总共比较2(n-1)次, 是O(n).
| p***y
发帖数: 637 | 8 每个候选数都必须和所以其他数比较一次，因为没有传递性
【在 z*******g 的大作中提到】
: 感觉最大应该这么定义：有唯一一个数与他所有数compare以后都显示这个数比较大。
: 那么从左取第一个数开始，与第二个compare，直到某个数比他大（如果到最后，那就
: 他最大）。然后从比他大的那个数开始重复上述过程。
: 例子如下： a, b, c, d, e, f, g, h, i, j, k
: 假设 a比b,c,d大，比e小，那么排除a, b,c,d；最大数只能在剩下的数里。
: 这样就相当回到了问题开始，不过砍掉了a，b，c，d
: 看了应该是 O（n）吧
| p***y
发帖数: 637 | 9 牛啊，原来和一般的寻找最大算法几乎一样
【在 z*******g 的大作中提到】
: 嗯，我倒是没有考虑不存在，如果一定存在且唯一，那扫一遍就好了
:
: 数,
: .
| J*****a
发帖数: 46 | 10 早说了你不信
【在 p***y 的大作中提到】
: 牛啊，原来和一般的寻找最大算法几乎一样
| | | f*****g
发帖数: 887 | 11 没明白怎么是o（n）
每次排除一些，但剩下的数还是需要和其他n-1个数做比较不是
怎么感觉还是o(n2)呢 | D*********G
发帖数: 193 | 12 这么说吧，假如一个数compare输了，他就一定不是最大数，因为最大数要比所有的数
都大。所以每次比较都会排除掉一个数，自然就可以o(N)搞定了
【在 f*****g 的大作中提到】
: 没明白怎么是o（n）
: 每次排除一些，但剩下的数还是需要和其他n-1个数做比较不是
: 怎么感觉还是o(n2)呢
| t*****3
发帖数: 112 | 13 re
数,
.
【在 I**********s 的大作中提到】
: 这个定义比较好: 有唯一一个数与他所有数compare以后都显示这个数比较大。
: 过程和find celebrity那个问题类似:
: 每次两个数比较, 比较小那个可以排除掉不是最大. 经过n-1次比较得到一个剩下的数,
: 再把这个数和其它n-1个数的每一个比较, 结果是要么这个数是最大要么最大不存在.
: 总共比较2(n-1)次, 是O(n).
| r*******e
发帖数: 340 | 14 这个解法好，赞。
【在 z*******g 的大作中提到】
: 感觉最大应该这么定义：有唯一一个数与他所有数compare以后都显示这个数比较大。
: 那么从左取第一个数开始，与第二个compare，直到某个数比他大（如果到最后，那就
: 他最大）。然后从比他大的那个数开始重复上述过程。
: 例子如下： a, b, c, d, e, f, g, h, i, j, k
: 假设 a比b,c,d大，比e小，那么排除a, b,c,d；最大数只能在剩下的数里。
: 这样就相当回到了问题开始，不过砍掉了a，b，c，d
: 看了应该是 O（n）吧
| q*c
发帖数: 9453 | 15 就是一遍比较， 记住最大的那个不久行了？？？
【在 b*****b 的大作中提到】
: 1.given 一个compare(T a, T b). 返回true if a>b, 返回false if a: 等的情况.
: 2. compare()是不transitive的, 比如说 a>b, b>c, 不能得到a>c. 有可能 c>a.
: 3. given 一个vector v.
: 求最快的找出v中的最大值.
: 我给了一个O(N^2). 但要求一个更快的.
| q*c
发帖数: 9453 | 16 根本不要这么复杂， 就是从前到最后一次比较， 最大的一定会自己跳出来， 根据定
义。
这是简单面试题， 呵呵／。
数,
.
【在 I**********s 的大作中提到】
: 这个定义比较好: 有唯一一个数与他所有数compare以后都显示这个数比较大。
: 过程和find celebrity那个问题类似:
: 每次两个数比较, 比较小那个可以排除掉不是最大. 经过n-1次比较得到一个剩下的数,
: 再把这个数和其它n-1个数的每一个比较, 结果是要么这个数是最大要么最大不存在.
: 总共比较2(n-1)次, 是O(n).
| q*c
发帖数: 9453 | 17 这不就是简单的找最大的方法？
【在 r*******e 的大作中提到】
: 这个解法好，赞。
|
|
