这是一道面试题。
给定一个文本文件,每一行包括:货件 ID、UPC 代码、数量
找出数量最多的 10 个行。
我的解决方案:
通过 C++
创建一个最小堆(大小为 10),并将数量作为比较对象。
将每个条目作为一个结构体读取,其中包含字段 { shipment ID, UPC code, quantity }
将其与10元素最小堆的顶部元素进行比较,
if > 用它替换顶部元素,否则读取下一个元素。
它是 O(n lg n)。
空间 O(1)。
更好的解决方案?
谢谢
最佳答案
旁注:您的时间成本实际上是 O(n),因为每个元素的插入时间是一个常数 (O(log 10))。
基本的想法是合理的——在成本方面你不会比 O(n) 做得更好——但与其滚动你自己的堆,不如使用 std::priority_queue
。
关于c++ - 在文本文件中查找 10 个最大数量行,其中包含 shipment ID 、 UPC code 、 quantity,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8452547/