solution to min and max in a big array

来源: sub101 于 2008-02-13 11:59:18 [] [旧帖] [给我悄悄话] 阅读数 : (296 bytes)

I have to say that meiying has the best solution. Just like "eagle playing in rain" pointed out, amei50's solution has constant 2 and meiying has constant 3/2.

My solution doesn't work because min != (A+B) /2 -ABS(A-B) / 2, where A and B are integers. It works when A+B is even number.

所有跟帖： 

• disagree!! -Jamesxu- ♂ 给 Jamesxu 发送悄悄话 (74 bytes) () 02/13/2008 postreply 12:25:50

• 回复：good luck dude! I hope we can hear good news -sub101- ♂ 给 sub101 发送悄悄话 (14 bytes) () 02/13/2008 postreply 12:29:10

• 你说的不对. -amei50- ♀ 给 amei50 发送悄悄话 (422 bytes) () 02/13/2008 postreply 12:47:36

• How about ( (A+B) - abs(A-B) ) / 2 ? -techy- ♀ 给 techy 发送悄悄话 (0 bytes) () 02/13/2008 postreply 12:50:13

• 回复：How about ( (A+B) - abs(A-B) ) / 2 ? -sub101- ♂ 给 sub101 发送悄悄话 (71 bytes) () 02/13/2008 postreply 13:00:50

• Why? 咱咋没找到反例？ -techy- ♀ 给 techy 发送悄悄话 (0 bytes) () 02/13/2008 postreply 14:47:22

• 回复：(5+2)/2=3 -sub101- ♂ 给 sub101 发送悄悄话 (38 bytes) () 02/13/2008 postreply 14:53:55

• 可咱把你的除2移到最后了，加减出来的肯定是偶数 -techy- ♀ 给 techy 发送悄悄话 (86 bytes) () 02/13/2008 postreply 15:04:31

• 回复：You are absolutely right! -sub101- ♂ 给 sub101 发送悄悄话 (0 bytes) () 02/13/2008 postreply 15:08:07

• ZT: You are absolutely right! -戏雨飞鹰- ♀ 给 戏雨飞鹰 发送悄悄话 (0 bytes) () 02/13/2008 postreply 16:48:05

• correct. -戏雨飞鹰- ♀ 给 戏雨飞鹰 发送悄悄话 (0 bytes) () 02/13/2008 postreply 16:56:19

• meiying has constant 3/2, not 3. 两两比较 only needs n/2. -戏雨飞鹰- ♀ 给 戏雨飞鹰 发送悄悄话 (6 bytes) () 02/13/2008 postreply 16:58:14

• check more carefully -Jamesxu- ♂ 给 Jamesxu 发送悄悄话 (196 bytes) () 02/13/2008 postreply 17:43:09

• Couldn't post & could not send QQ to u. 说是有禁字。 -戏雨飞鹰- ♀ 给 戏雨飞鹰 发送悄悄话 (0 bytes) () 02/13/2008 postreply 18:51:29

• 回复：check more carefully -戏雨飞鹰- ♀ 给 戏雨飞鹰 发送悄悄话 (197 bytes) () 02/13/2008 postreply 19:20:15

• make it clear this way: -戏雨飞鹰- ♀ 给 戏雨飞鹰 发送悄悄话 (262 bytes) () 02/13/2008 postreply 19:40:44

• 回复：loop n/2 times and 3 comparisons each time -sub101- ♂ 给 sub101 发送悄悄话 (0 bytes) () 02/13/2008 postreply 20:17:25

• see my explaination -Jamesxu- ♂ 给 Jamesxu 发送悄悄话 (608 bytes) () 02/14/2008 postreply 03:04:01

• btw, memory read means memory look up here -Jamesxu- ♂ 给 Jamesxu 发送悄悄话 (130 bytes) () 02/14/2008 postreply 04:55:42

• Right! The average value for the operation of Amei's is also 3n/ -戏雨飞鹰- ♀ 给 戏雨飞鹰 发送悄悄话 (0 bytes) () 02/14/2008 postreply 07:51:16

请您先登陆，再发跟帖！