可能的重复：
在数组中找到第二个最大的元素，具有最小的比较数
我可以知道如何实现在 O(n+logn) 时间内搜索最大和第二大数字吗？先感谢您。
最好的问候， Pidig
问问题
1816 次
3 回答
7
请注意，O(n+logn) = O(n)在列表上迭代两次是O(n).
- 迭代一次以找到最大值并删除/标记它，
- 然后第二次迭代找到新的最大值（第二大元素），
因为它在数组上迭代常数次，所以算法是O(n).
对于通用k最大元素：您可以使用 min heap inO(nlogk)或selection algorithm in O(n)- 如本答案中所述，但对于 2 个最大元素 - 这些方法过于矫枉过正。
于 2012-05-31T14:38:18.177 回答
3
我猜你的意思是 n + log(n) - 2 个比较。
这是你如何做到的。
比较两组中的元素。即制作 n/2 组，每组两个元素。
以这种方式继续使用 n/4、n/8、n/16 等，直到获得第一个（最大）元素。
现在下一个最大的元素必须在此方法中的第一个元素的失败者中。因此 log(n) 对此进行了更多比较。
准确地说，这将需要 n + log(n) - 2 次比较。
于 2012-05-31T14:51:15.843 回答
1
您实际上可以O(n)及时做到这一点：选择算法
于 2012-05-31T14:38:51.833 回答