算法與數據結構25：資源限制類題目

• 資源限制技巧匯總
• 題目一
• 題目二
• 題目三
• 題目四
• 題目五
• 題目六
• 題目七

創(chuàng)新互聯長期為近1000家客戶提供的網站建設服務，團隊從業(yè)經驗10年，關注不同地域、不同群體，并針對不同對象提供差異化的產品和服務；打造開放共贏平臺，與合作伙伴共同營造健康的互聯網生態(tài)環(huán)境。為涿州企業(yè)提供專業(yè)的成都網站設計、做網站、成都外貿網站建設公司，涿州網站改版等技術服務。擁有10多年豐富建站經驗和眾多成功案例,為您定制開發(fā)。資源限制技巧匯總

1、布隆過濾器用于集合的建立與查詢，并可以節(jié)省大量空間
2、一致性哈希解決數據服務器負載管理問題
3、利用并查集結構做島問題的并行計算
4、哈希函數可以把數據按照種類均勻分流
5、位圖解決某一范圍上數字的出現情況，并可以節(jié)省大量空間
6、利用分段統(tǒng)計思想，并進一步節(jié)省大量空間
7、利用堆、外排序來做多個處理單元的結果合并

題目一

32為無符號整數的范圍是0~4294967295，現在有一個正好包含40億個無符號整數的文件，可以使用最多1GB的內存，怎么找到出現次數最多的數？
排序？不行，內存只有1G，無法在內存排序
1、假設1G內存，使用hash表最多只能裝下1千萬條記錄，那么40億除以1千萬，等于400，準備400個文件
2、然后每一個數，通過hash函數，算出一個hash值，模400，得到一個文件編號，該數發(fā)送到對應文件
3、此時同一個數字，只會進入一個文件，文件里面存的是該數字出現的次數
4、這樣就搞成了400個文件，此時每次加載一個文件，遍歷文件的每條記錄，抓出出現次數最多的
5、最后這400個出現次數最多的數PK一下，得出整體出現次數最多的數。
6、如果發(fā)現一個文件大小過大，在內存還是裝不下，那么文件就搞500個、600個…

如果題目要求返回出現次數最多的所有數，那么就拿著這個次數，到每個文件中再找一遍，看有沒有出現這么多次的數，有的話就全部抓出來，返回。

題目二

32位無符號整數的范圍是0~4294967295，
現在有一個正好包含40億個無符號整數的文件，
所以在整個范圍中必然存在沒出現過的數。
可以使用最多1GB的內存，怎么找到所有沒有出現過的數？
set去重統(tǒng)計？不行，內存會爆掉。
使用位圖，8個bit才一個直接，那么就準備4294967295bit長度的位圖進行統(tǒng)計。
如果實現bit數組？使用基礎類型拼，長度為10的int數組，等于320bit長度的bit數組，第i個bit就是arr[i / 32]這個數的第i%32位
那么這一位代表的數是否存在，就這樣計算：
int status = arr[i / 32] & (1<< (i%32)) != 0 ? 1 : 0;
如果status是1，那么就是存在，0就是不存在。

【進階】
內存限制3KB，但是只用找到以沒出現過的數即可。
3KB大約能存下750個整形，那么準備一個離750最近的2的某次方，得到512，那么申請512長度的數組
此時可以把0~4294967295均分為512份（512個文件），每一份負責負責的范圍的長度是8388608
這樣，肯定在每個范圍上存儲數不滿8388608的情況，找到這個不滿的范圍，再分512份，再找不滿的小范圍，再分512份…，幾次過后就能找到沒出現過的1個數。

【進階】
內存中只能申請有限幾個遍歷，但是只用找到以沒出現過的數即可。
申請兩個遍歷L和R，對0~4294967295進行二分（兩個文件）
統(tǒng)計兩邊出現的數的個數
其中有一邊肯定不滿，再對不滿的一邊進行二分，還是用兩個變量L、R統(tǒng)計兩邊范圍出現的數的個數
如此不斷二分，最終會找到沒出現過的1個數

題目三

有一個包含100億個URL的大文件，假設每個URL占用64B，
請找出其中所有重復的URL
如果允許失誤率，使用布隆過濾器
如果不允許，使用hash分流，分到不同小文件，看小文件是否有重復的。

【補充】
某搜索公司一天的用戶搜索詞匯是海量的（百億數據量），
請設計一種求出每天人們Top100詞匯的可行辦法。

題目四

32為無符號整數的范圍是0~4294967295，
現在有40億個無符號整數，
可以使用最多1GB內存，
找出所有出現了兩次的數。

用兩個bit位表示一個數出現的次數，比如那0bit為何1bit為表示0這個數出現的次數，00表示出現0次，01表示出現1次，10，表示出現兩次，11表示出現3次或以上。
這樣1個byte表示4個數。
但是4294967295除以4，超過了1G，那就繼續(xù)用上面分段統(tǒng)計的辦法。
也就是：位圖 + 分段統(tǒng)計，先統(tǒng)計前面一半（0~2^31）出現兩次的數，在統(tǒng)計后面一半的

題目五

32位無符號整數的范圍是0~4294967295，
現在有40億個無符號整數
可以使用最多3KB的內存，怎么找到這40億個整數的中位數？

bfprt？不行，內存會爆掉。

3KB大約能存下750個整形，那么準備一個離750最近的2的某次方，得到512，那么申請512長度的數組arr。
此時可以把0~4294967295均分為512份（512個文件），每一份負責負責的范圍的長度是8388608。
數組arr中每一個數統(tǒng)計自己范圍內出現的數的個數。
中位數是第20億個數，那么看數組arr累加到大于等于20億，是數組arr中的第幾個數。
假設arr[129]沖動了20億，那么中位數一定在第129號文件。
然后以相同的方法，對129號文件分512份，數組arr統(tǒng)計每一份中出現的數的個數…循環(huán)往復，最終找到中位數。

題目六

32位無符號整數的范圍是0~4294967295，
有一個10G大小的文件，每一行都裝著這種類型的數字，
整個文件是無序的，給你5G的空間，
請你輸出一個10G大小的文件，就是原文件所有數字排序的結果。

現在不看5G內存，假設內存嚴重不足，只能存幾條記錄
那么準備一個堆，大根堆，只存3條記錄，存的是數字和出現的次數
申請1個10G的文件，用于存放結果

遍歷文件，在堆中記錄數字以及該數出現的次數：
假設遍歷到3，記錄 3 =>1，表示3出現1次
再遍歷到3，記錄 3 =>2，表示3出現2次
遍歷到9，記錄 9 =>1
遍歷到7，記錄 7 =>1
遍歷到8，堆滿了，彈出 9 =>1，記錄8 =>1
遍歷到6，堆滿了，彈出 8 =>1，記錄6 =>1
…
文件遍歷完了，堆中就記錄了整個文件中前3小的數，出現的次數
假設是
1 =>1000
3 =>2000
5 =>1000
然后在10G的文件中，數字1寫1000次，數字3寫2000次，數字5寫1000次

然后用1個遍歷記錄5，表示上一次遍歷到的大的數
再搞一遍這個遍歷，在堆中記錄數字以及該數出現的次數，但是小于等于5的數字不再記錄
…
這樣一直搞，直至所有的數都統(tǒng)計完（某一次循環(huán)，堆沒放滿），10G排序號的文件返回。

題目七

一個大文件，返回里面出現的數的前100名。
解法：分成不同的小文件，通過hash分流把數字分發(fā)到不同文件，每個文件統(tǒng)計Top100，然后在內存做歸并排序。

你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧

網站欄目：算法與數據結構25：資源限制類題目-創(chuàng)新互聯
轉載源于：http://m.rwnh.cn/article16/cecegg.html

成都網站建設公司_創(chuàng)新互聯，為您提供域名注冊、微信小程序、商城網站、網站設計公司、網站設計、網站改版

廣告

聲明：本網站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯