如何理解《程式設計珠璣》上的這道題？

1樓：鄧鋆

二分法不是最快的，儘管在佔據額外空間（寫額外的兩個檔案）的情況下，時間複雜度成功的達到了下限N，但顯然不夠完美。

用hash表達4G個數字是否出現過，只需要4G個二進位制位而非4G個位元組，所以就算是直接硬儲存，也只需要區區512M空間即可。對於現在通行的計算機裝置而言，記憶體已經足夠了。

如果記憶體進一步不足，那麼使用二分法縮小range鎖定目標，到記憶體限制之內再進行hash 也不失為乙個可靠的辦法。另外，所謂的二分未免太小家子氣了一點，效率更高一點的辦法應該是以range分，舉例來說，我們擁有區區8K記憶體，那麼可以：

pass 1、每個桶用4個位元組來計數，進行一次統計，可以統計2K個桶，每個桶內最多有2M個數字（所以需要4byte），最後找到乙個缺了資料的桶。

pass 2、每個桶用2個位元組來計數，進行一次統計，可以統計4K個桶，每個桶內最多僅有512個數字（所以需要2byte），最後找到乙個缺了資料的桶。

pass 3、每個桶只需要用1個bit來計數，進行一次統計，可以統計完512個數字。

只用了3個pass就完成了二分法花費了32個pass完成的工作。

關於儲存這邊，可以選擇兩個接受的方案之一：

1、每乙個pass有多少個桶，就生成多少個檔案。

2、除了第乙個pass，每乙個pass重新掃瞄一遍上乙個pass的結果並過濾，一邊把過濾結果輸出到外存，一邊進行這乙個pass的運算。這樣下乙個pass可以直接使用過濾結果。

貌似是我之前錯誤理解了4 billion這個概念，如此看來4 billion是4,000,000,000，而不是4,294,967,296，如果這樣，那麼二分法一定會有一邊缺少數字，同樣，我所提出的「桶」法也一定會有至少乙個桶缺少了數字。確實跟重複數字無關，是總數需要少於2^32。哪怕少1也行。

之前的描述：

另外，這個演算法和「二分法」一樣，都有乙個前提，就是目標資料中不存在重複數字。但是從題目中我沒明確看出這個條件，僅僅提到總數最多4b個。如果存在重複數字的話，暫時還沒想到切實可靠，低複雜度上限的好辦法，不過一次的hash（512M空間那個）還是可行的。