推 yero:呃 我信裡寫的是general的數列耶 >.< 06/16 01:15
※ 引述《lqke (Incessant philandering)》之銘言：
: ※ 引述《kikily0920 (等待的感覺......)》之銘言：
: : 請問你沒有消息多久了呢?
: : 一般來說 面試後若是覺得你不錯
: 聽起來是bye了
: 不過照今天商週講法
: 台灣約有一千人投履歷
: 目前只有四個人錄取
: 也不用難過囉
: 對了
: 乾脆討論一下商週上講的一道面試例題
: 請用程式寫一個演算法找七個數當中的中位數
: Google要求只能比七次
: 嗯 題目可能有點不完善
: 不過歡迎大家討論
: 我是除了先用傳統的quick sort排序外想不到還能怎麼找了
前鎮子吃飽飯沒事幹剛好寫過這個題目...
見冼鏡光「C名題精選百則」 P5-11 問題5-6 求中位數
推文中有人提到了quicksort做一半這個答案沒錯(可是不用recursive喔)
Mark Allen Weiss 的書也有提到(不過個人認為寫的沒冼老師的好)
不過用這種解法最快也要2N次，7次是什麼神奇演算法就不知道了
不過商周的東西笑笑就好
----
更正:有人來信說可以壓縮到7次，我想了一下在特殊情形下的確可以
data: 4,7,6,5,3,2,1
4165327
^ ^
i j
4125367
4123567
1234567
假如是給定特定的7個數字要求七次找出median沒問題
(我猜這應該是google原來真正的題目)
假如是隨機7個數字就不太可能
大家一起上 topcoder 練功吧!
※ 編輯: lg31cm 來自: 59.112.36.17 (06/16 01:13)