c++ - 在文本文件中查找 10 个最大数量行，其中包含 shipment ID 、 UPC code 、 quantity

Question

这是一道面试题。

给定一个文本文件，每一行包括:货件 ID、UPC 代码、数量

找出数量最多的 10 个行。

我的解决方案:

通过 C++

创建一个最小堆(大小为 10)，并将数量作为比较对象。

将每个条目作为一个结构体读取，其中包含字段 { shipment ID, UPC code, quantity }

将其与10元素最小堆的顶部元素进行比较，

if > 用它替换顶部元素，否则读取下一个元素。

它是 O(n lg n)。

空间 O(1)。

更好的解决方案？

谢谢

Answer 1

旁注:您的时间成本实际上是 O(n)，因为每个元素的插入时间是一个常数 (O(log 10))。

基本的想法是合理的——在成本方面你不会比 O(n) 做得更好——但与其滚动你自己的堆，不如使用 std::priority_queue。