查找100個不同文件中的前10個整數

我是一名新鮮人，正準備面試。在我最近的採訪中，我被問到一個問題，爲此我找不到合適的答案。查找100個不同文件中的前10個整數

我給了大約100個文件，每個文件都包含大量逗號分隔的整數。我必須在整個文件中找到前10個整數。我試圖用堆來解決它。但是我對這個過程的時間複雜性感到困惑。任何幫助將不勝感激，謝謝。

2013-10-29 shashi.kr

相關/可能重複 - [查找前10個搜索項的算法]（http://stackoverflow.com/questions/3260653/algorithm-to-find-top-10-search-terms?rq=1）。 – Dukeling

文件是否包含唯一編號？也就是說，數字42可以在單個文件中多次出現？ –

你在尋找10個最大的整數，還是10個整數中出現次數最多的整數？ –

我認爲你使用堆數據結構是正確的軌道。

你可以處理文件並行併爲每個文件10

當你通過文件迭代你插入值最小堆，直到填滿（你可以保持大小的最小堆到n

if current_value > min_heap.current() 
    min_heap.extract() 
    min_heap.insert(current_value)

你必須到n值和最壞的情況下遍歷大小10），然後在位置11值是如果該文件是按升序排序。在這種情況下，您將不得不提取最小值併爲位置11到n中的所有值插入一個新值。堆操作將爲O（log n），爲每個文件提供O（n * log n）的總體運行時間。

在這一點上，你有m（文件數量）每個大小爲10的小堆。在這裏，你可以使用最後一個小堆來存儲包含在m個最小堆中的十個最大數字。這個計算將是O（m），因爲此時所有的堆都是最大尺寸10，一個常數。

整體運行時間爲O（n * log n + m）。 m可能比n小得多，所以在朋友中我們可以說O（n * log n）。即使你沒有並行完成第一步，它也會是O（m * n * log n + m），但是如果n支配m，我們可以說O（n * log n）。

2013-10-29 08:35:31 dannyp

十大最大整數感謝您的算法，它幫助我擺脫了我的困惑:) –

您的算法不起作用。想象一下，你正在尋找三個文件中最常用的數字（只有一個）。在這些文件中，數字7在每個文件中出現8次。但它是每個文件中第二個最常見的數字。在每個文件中，都會有更多的其他數字出現，但總體來說，數字7的出現次數比其他任何數字都要多。你的算法會給出錯誤的答案。 –

我誤解了「前十個整數」。我認爲這是文件中最大的整數，而不是整數最多的整數。 – dannyp

回答