查找貨運ID，UPC代碼，數量

Question

文本文件中最大的10行數據這是一個面試問題。

鑑於一個文本文件，每一行包括：貨物ID，UPC代碼，數量

找到10條最大的量線。

我的解決方案：

用C++

使最小堆（具有尺寸10），數量爲比較對象。

閱讀每個條目爲結構與字段{貨物ID，UPC代碼，數量}

與頂部元件比較它的10元件最小堆，

如果>更換頂端元件用它，否則讀下一個元素。

它是O（n lg n）。

Space O（1）。

更好的解決方案？

感謝

Answer 1

邊注：您的時間成本實際上是O（n），因爲每個元素的插入時間是一個常數（O（日誌10））。

的基本思路是聲音 - 在成本方面，你不會比O（N）做的更好 - 但不是滾動您自己的堆，用std::priority_queue。