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 的大作中提到】 : 这个解法好,赞。
|
|