源_小K算法

說起刷題，想必對(duì)于每一個(gè)已經(jīng)在搬磚的讀者都不陌生，曾經(jīng)那段日日刷題、夜夜復(fù)習(xí)的痛并快樂的日子，你還記著嗎？

今天分享一個(gè)又難又簡(jiǎn)單的騰訊面試題，不保證你下次面試會(huì)遇上，但是你下次遇上了一定會(huì)！

算法面試題

有64匹馬，8條賽道，要找出最快的4匹馬，最少要幾次呢？

初步思考

很多同學(xué)可能第一反應(yīng)就是，這個(gè)問題肯定不簡(jiǎn)單，應(yīng)該有一些技巧，但技巧是啥呢，又一時(shí)想不出來。

其實(shí)呢，先別想得太復(fù)雜了，比如我現(xiàn)在就問你一個(gè)問題，有沒有可能存在有一匹馬不用跑？

答案當(dāng)然是不行。

因此每匹馬都需要跑一次，這就是這道題目的條件。

題目分析

那也就是每一匹都得先跑一次，64匹，8個(gè)賽道，那就先分8組跑8次。

每一組都會(huì)得到8匹的相對(duì)速度，也就是在同一組內(nèi)的名次。

為了方便描述，我們用編號(hào)來表示。如A組里面的名次分別用來表示。

因?yàn)槲覀冎恍枰页鲎羁斓?匹，那么肯定不屬于最快的4匹，同理把每一組的后4名先排除。

現(xiàn)在每一組內(nèi)都有相對(duì)名次，但不同的組間是不知道的。如果把A組和B組放在一起，下面的情況都可能存在。

因?yàn)槭且易羁斓模赃x擇每組的第一名再出來跑一次，這樣落后的第一名所在的整組都可以排除。為了描述方便，把最快到最慢的第一名所在的組依次重新命名為A，B...H組。

組間的第一名有了名次關(guān)系，可以發(fā)現(xiàn)一定不屬于前4名，因?yàn)槎荚谒麄兦懊妗Ｍ砜膳懦Ｍ瑫r(shí)是最快的，一定屬于前4。那接下來只需在剩下的9匹中找出前3。

除去，其余8匹跑一次。如果在第3名或者更后，那說明已經(jīng)選出了前3名，也不用再跑了，否則再取前3和一起跑一次，即可得結(jié)果。

最多11次一定可以選出最快的4匹。

其他問題

主要的問題集中在以下幾方面_

1、問題一

問_直接用計(jì)時(shí)器，每次8匹馬分8次跑完，按時(shí)間順序排序不就行了嗎？

答_只能說不知道有同學(xué)會(huì)這樣想，那確定應(yīng)該在題目上加這個(gè)限制，不能用計(jì)時(shí)器。面試題應(yīng)該也不會(huì)考察你會(huì)不會(huì)用計(jì)時(shí)器呀，對(duì)不？

那小K再補(bǔ)充一下，只能利用相對(duì)名詞通過邏輯推理來找出前4名。

題目沒有說明的限制這確實(shí)是一個(gè)漏洞，但這樣想那漏洞就多了去了呀，哈哈。

2、問題二

問_馬每次跑的速度都是一樣的嗎？

答_這個(gè)也確實(shí)應(yīng)該加上，默認(rèn)每匹馬的速度不變，不考慮馬兒的生理因素哈。

3、問題三

問_如果有并列名次的馬兒怎么辦？

答_這個(gè)也確實(shí)應(yīng)該加上，如果8匹馬速度都一樣，那跑一次就什么信息也得不到，不得不說大家考慮得還真是周到呀。

4、問題四

問_題目說得最少多少次，為什么最后又說最多11次？

答_可能小K描述不夠準(zhǔn)確，那小K再重新描述一下_在某種小概率的巧合下，原文也說明了，就是A3排在第3或者更后，那么最少就是10次。不考慮特殊場(chǎng)景最少就是11次，可以穩(wěn)定求解。

這種思維題，其實(shí)是很難直接就想清楚整個(gè)過程。可以先想得簡(jiǎn)單一點(diǎn)，往下推一步再看，逐步推進(jìn)就可以引導(dǎo)出正確的結(jié)果了。