在1,000,000,000总价值中找到最大的10,000
我有一个文件，其中有1,000,000个浮动值。我需要找出最大的价值。
我在想：
- 读取文件
- 将字符串转换为浮动
- 将浮点数放入最大堆(最大值为根的堆)。
- 在所有值都在堆中之后，删除根10,000次，并将这些值添加到list/arraylist中。
我知道我会
- 1,000,000插入到堆中
- 从堆中移除10,000次
- 10,000插入返回列表
这是一个好的解决办法吗？这是做作业用的。
回答 4
Stack Overflow用户
发布于 2012-09-20 17:22:49
你的解决方案大多是好的。它基本上是一个在获得K元素之后停止的heapsort，这将提高从O(NlogN) (对于完整排序)到O(N + KlogN)的运行时间。这里N= 1000000，K= 10000。
但是，您不应该首先对堆执行N个插入操作，因为这将采用O(NlogN) --而是使用heapify操作，它在线性时间内将数组转换为堆。
如果不需要对K数进行排序，则可以使用selection algorithm在线性时间内找到Kth最大数，然后输出大于它的所有数字。这给出了一个O(n)解决方案。
Stack Overflow用户
发布于 2012-09-20 17:21:50
使用mergesort(在最坏情况下使用log n操作)将1,000,000个整数排序到一个数组中，然后直接获得最后的10000，怎么样？
Stack Overflow用户
发布于 2012-09-20 18:09:24
排序是昂贵的，而且您的输入集并不小。幸运的是，你不关心秩序。你只需要知道你有最上面的X数。所以，别排序。
如果你不是在寻找1,000,000中的前10,000名，而是在100项中寻找前1名(即单一的最大值)，那么您将如何解决这个问题？您只需要跟踪到到目前为止看到的最大值，并将其与下一个和下一个数字进行比较，直到您找到更大的值或输入不足为止。你能把这个想法扩大到你所看到的输入大小吗？什么是大-O(提示:您只查看每个输入号码一次)？
最后注意，既然你说这是家庭作业:如果你刚刚在课堂上学习了堆，而你认为你的老师/教授正在寻找堆解决方案，那么是的，你的想法是好的。
https://stackoverflow.com/questions/12517579
复制相似问题
腾讯云开发者
