算法题008 快速找出故障机器
快速找出故障機(jī)器
?
題目描述
關(guān)心數(shù)據(jù)挖掘和搜索引擎的程序員都知道，我們需要很多的計(jì)算機(jī)來存儲(chǔ)和處理海量數(shù)據(jù)。
然而，計(jì)算機(jī)難免出現(xiàn)硬件故障而導(dǎo)致網(wǎng)絡(luò)聯(lián)系失敗或死機(jī)。為了保證搜索引擎的服務(wù)質(zhì)量，我們需要保證每份數(shù)據(jù)都有多個(gè)備份。
簡單起見，假設(shè)每個(gè)機(jī)器存儲(chǔ)一個(gè)標(biāo)號為ID的記錄（ID是小于十億的整數(shù)），假設(shè)每份數(shù)據(jù)都保存兩個(gè)備份，這樣就有兩個(gè)機(jī)器儲(chǔ)存了同樣的數(shù)據(jù)。
1.在某個(gè)時(shí)間，如果得到一個(gè)數(shù)據(jù)文件ID的列表，是否能夠快速地找出這個(gè)表中僅出現(xiàn)一次的ID？
2.如果已經(jīng)知道只有一臺(tái)機(jī)器死機(jī)（也就是說只有一個(gè)備份丟失）呢？如果有兩臺(tái)機(jī)器死機(jī)呢（假設(shè)同一個(gè)數(shù)據(jù)的兩個(gè)備份不會(huì)同時(shí)丟失）？
?
我的解法
這個(gè)題目肯定要考慮大量數(shù)據(jù)的處理，即需要重點(diǎn)考慮效率問題。
首先，ID是小于十億的整數(shù)，這說明用一個(gè)long型（4個(gè)字節(jié)）可以表示ID，不會(huì)超出表示范圍，所以這點(diǎn)不用擔(dān)心。
根據(jù)題目特點(diǎn)，得到ID列表后，可以考慮一種像是玩撲克牌游戲的做法，找一個(gè)數(shù)組來盛放遍歷的數(shù)（想象成摸牌），找到成對的就丟棄（或者你也可以把這個(gè)配對過程想象成連連看）。
最后將所有數(shù)字遍歷完之后還留下的就是單獨(dú)的ID。
這樣時(shí)間復(fù)雜度是O(n * n)，因?yàn)樾枰張牌，并且每摸一張牌都需要和手中的牌進(jìn)行查詢配對。
下面是書中的解法，看完之后才知道我的解法真是弱爆了，為什么沒想到哈希表呢。
?
解法一
直接遍歷列表，利用一個(gè)數(shù)組記錄下每個(gè)ID出現(xiàn)的次數(shù)，遍歷完畢之后，出現(xiàn)次數(shù)小于2的ID就是我們想要的結(jié)果。
假設(shè)有N個(gè)ID，且ID的取值在0~N-1之間，這個(gè)解法占用的時(shí)間復(fù)雜度為O(N)，空間復(fù)雜度為O(N)。
時(shí)間復(fù)雜度已經(jīng)相當(dāng)理想，但是空間復(fù)雜度不夠理想，如果ID的數(shù)量多達(dá)幾個(gè)G甚至幾十G，這樣的空間復(fù)雜度在實(shí)際的運(yùn)算中就會(huì)帶來效率問題。
?
解法二
考慮到大部分ID的出現(xiàn)次數(shù)都等于2，這些ID的信息并不是必要的，所以不必存儲(chǔ)。
因此，可以把解法一數(shù)組中等于2的元素清空，然后用來存儲(chǔ)下一個(gè)機(jī)器ID的出現(xiàn)次數(shù)，這樣就可以減少需要的空間。
具體方法如下：遍歷列表，利用哈希表記下每個(gè)ID出現(xiàn)的次數(shù)，每次遇見一個(gè)新的ID，就向哈希表中增加一個(gè)元素；如果這個(gè)ID出現(xiàn)的次數(shù)為2，那么就從哈希表中刪除這個(gè)元素，最后剩下的ID就是我們想要的結(jié)果。
這個(gè)算法的空間復(fù)雜度在最好情況下可以達(dá)到O(1)，在最壞的情況下仍然是O(N)。
?
解法三
對于第一問，假設(shè)列表中僅有一個(gè)ID出現(xiàn)了一次，那么可以考慮用異或關(guān)系來幫忙找到結(jié)果。
因?yàn)?span style="background-color:#ffff00;">異或運(yùn)算的定義是相同為假相異為真，異或運(yùn)算滿足交換律和結(jié)合律。
所以，所有ID的異或值就等于這個(gè)僅出現(xiàn)一次的ID。（兩兩相同的都得到0，0和任何值異或等于原來的任何值）
這種情況下，時(shí)間復(fù)雜度為O(N)，空間復(fù)雜度為O(1)。
?
對于第二問，由于有兩個(gè)ID僅出現(xiàn)了一次，設(shè)它們?yōu)锳和B，那么所有ID異或的結(jié)果是A異或B，但還是無法確定A和B的值。
可以進(jìn)行分類討論：
（1）A == B
這時(shí)A異或B等于零，丟失的是同一份數(shù)據(jù)的兩個(gè)拷貝，可以通過求和的方法求得A和B，即，所有ID值的和減去所有正常的ID之和，除以2得到A和B。
（2）A !=B
這時(shí)A異或B不等于零，那么這個(gè)異或值的二進(jìn)制位中某一位為1，此時(shí)A和B中有且僅有一個(gè)數(shù)的相同位上也為1。
我們就把所有的ID分成兩類，一類在這位上為1，另一類在這位上為0。A和B分別位于這兩類中。
我們分別計(jì)算這兩類的異或和，即可得到A和B的值。（太巧妙了！）
?
解法四
對于第一問，缺失一個(gè)ID：
預(yù)先計(jì)算并保存好所有ID的求和（“不變量”），順序列舉當(dāng)前所有剩下的ID，對它們求和，然后用所有ID的求和減去當(dāng)前剩下所有ID的和，結(jié)果就是死機(jī)的機(jī)器的ID值。
時(shí)間復(fù)雜度為O(N)，空間復(fù)雜度為O(1)，和解法三一樣是計(jì)算復(fù)雜度最優(yōu)的算法。
?
對于第二問，我們考慮所有的情況，即兩個(gè)ID可以相同也可以不同。
用上面的方法可以得到這兩個(gè)ID的和。我們構(gòu)造出一個(gè)方程: x + y = a; a已知。
第二個(gè)方程有很多構(gòu)造方法，比如可以用所有ID的乘積計(jì)算出另一個(gè)不變量，除以所有剩下的ID，結(jié)果得到兩臺(tái)死機(jī)機(jī)器的ID的乘積，即x * y = b。
這樣聯(lián)立兩個(gè)方程之后，可以解出x和y的值。
時(shí)間復(fù)雜度為O(N)，空間復(fù)雜度為O(1)。
第二個(gè)方程構(gòu)造也可以考慮平方和的方法。
?
參考資料
《編程之美》1.5節(jié)
總結(jié)
以上是生活随笔為你收集整理的算法题008 快速找出故障机器的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 用python编写daemon监控进程并
- 下一篇： 服务器安全浅谈