about max and min in an array

来源: sub101 于 2008-02-13 07:15:12 [] [旧帖] [给我悄悄话] 阅读数 : (412 bytes)

I hate myself very much! I promised that I would reply the posted related to ... However, I cannot help myself after I read the posts under.

For max and min in an array, no comparison needed. Assuming we have two numbers A and B, the min = (A+B)/2-ABS((A-B)/2) and max=(A+B)/2+ABS((A-B)/2). Recursively travel through the array and you would find the min and max.

It is a simple algorithm.

所有跟帖： 

• you are right!! I thought the same way -galdfly- ♀ 给 galdfly 发送悄悄话 (0 bytes) () 02/13/2008 postreply 07:18:03

• 有必要把简单问题复杂化吗 -amei50- ♀ 给 amei50 发送悄悄话 (0 bytes) () 02/13/2008 postreply 07:21:10

• 回复：It simplifies the problem. -sub101- ♂ 给 sub101 发送悄悄话 (135 bytes) () 02/13/2008 postreply 07:24:26

• 请看我下面的帖子吧，和偶数奇数有什么关系？ -amei50- ♀ 给 amei50 发送悄悄话 (87 bytes) () 02/13/2008 postreply 07:27:28

• 回复：My bad! I didn't read your solution carefully. -sub101- ♂ 给 sub101 发送悄悄话 (163 bytes) () 02/13/2008 postreply 07:35:01

• 回复：回复：My bad! I didn't read your solution carefully. -sub101- ♂ 给 sub101 发送悄悄话 (0 bytes) () 02/13/2008 postreply 07:37:29

• 回复：回复：But I am not sure -sub101- ♂ 给 sub101 发送悄悄话 (55 bytes) () 02/13/2008 postreply 07:38:49

• 1 abs > 1 compare -Jamesxu- ♂ 给 Jamesxu 发送悄悄话 (507 bytes) () 02/13/2008 postreply 08:35:15

• sub01's calculation might takes long cpu circle -Jamesxu- ♂ 给 Jamesxu 发送悄悄话 (380 bytes) () 02/13/2008 postreply 08:24:43

• 回复：multiply by 2 is same as bit shift -sub101- ♂ 给 sub101 发送悄悄话 (73 bytes) () 02/13/2008 postreply 08:48:02

• 回复：sub01's calculation might takes long cpu circle -DCD- ♂ 给 DCD 发送悄悄话 (78 bytes) () 02/13/2008 postreply 09:04:19

• 回复：回复：it doesn't work! -sub101- ♂ 给 sub101 发送悄悄话 (85 bytes) () 02/13/2008 postreply 09:09:04

• 回复：it doesn't work! - Yes mistake- thx -DCD- ♂ 给 DCD 发送悄悄话 (274 bytes) () 02/13/2008 postreply 09:37:47

• 我没算错的话，你的space complexity is good, O(N), -yellowlemon- ♀ 给 yellowlemon 发送悄悄话 (182 bytes) () 02/13/2008 postreply 08:17:13

• yes, both sub01 and amei has O(0) time complexity -Jamesxu- ♂ 给 Jamesxu 发送悄悄话 (0 bytes) () 02/13/2008 postreply 08:25:14

• sorry, i meant O(n), not O(0) which means constant -Jamesxu- ♂ 给 Jamesxu 发送悄悄话 (0 bytes) () 02/13/2008 postreply 08:35:59

• sorry I made a mistake, ur algorithm is not bad comparing to -yellowlemon- ♀ 给 yellowlemon 发送悄悄话 (47 bytes) () 02/13/2008 postreply 08:26:16

• sort >= O(nlogn) -Jamesxu- ♂ 给 Jamesxu 发送悄悄话 (0 bytes) () 02/13/2008 postreply 08:28:12

• yes, right. long time did not pick up algorithms book coz -yellowlemon- ♀ 给 yellowlemon 发送悄悄话 (91 bytes) () 02/13/2008 postreply 08:30:24

• ABS什么意思？谁帮我解说一下sub101 的算法？谢谢 -好汉- ♂ 给 好汉 发送悄悄话 (0 bytes) () 02/13/2008 postreply 08:50:47

• ABS原来是function,呵呵，误解了 -好汉- ♂ 给 好汉 发送悄悄话 (0 bytes) () 02/13/2008 postreply 08:55:54

• abs = absolute,取决对值。actually I quite like his algorithm -yellowlemon- ♀ 给 yellowlemon 发送悄悄话 (0 bytes) () 02/13/2008 postreply 08:55:59

• 开始想别的东西了，看第二遍才反应过来，谢谢回复 -好汉- ♂ 给 好汉 发送悄悄话 (0 bytes) () 02/13/2008 postreply 08:59:24

• 回复：thanks for all your inputs. -sub101- ♂ 给 sub101 发送悄悄话 (161 bytes) () 02/13/2008 postreply 09:05:07

• 回复：It was one of the questions I was asked -sub101- ♂ 给 sub101 发送悄悄话 (146 bytes) () 02/13/2008 postreply 09:28:23

请您先登陆，再发跟帖！