寻找最大的 2 个数字 - 计算机科学

StackOverflow https://stackoverflow.com/questions/1648976

  •  22-07-2019
  •  | 
  •  

题

我正在尝试找出一种算法来查找数字列表中最大的 2 个数字。

最高的数字可以在 n-1 个阶段中找到，也许可以通过执行冒泡排序的第一步或类似的操作。对我来说，似乎平均可以在总共 1.5n 次比较中找到下一个最高数字。

我的教授给我们布置了作业，要求我们编写一个算法，在 n + log(n) 比较中找到最大的 2 个数字。这可能吗？有什么想法、建议吗？

编辑：当我说 n + log(n) 时，我指的不是 O(n + log n)，而是指 n + log n

有帮助吗？

解决方案

是，有可能做到这一点在不超过（N + log n）的多。我真的不能告诉你如何在不放弃的答案，但让我试试。 :-)

采取n个数字，它们在对在一个时间进行比较。就拿小区（N / 2）“赢家”，并重复，“像一个二进制树”。问题：有多少的比较没有考虑找一个最大？有多少人没有这个“赢家”战胜？向谁可能的第二大已失去了什么？那么有多少比较它现在需要找到第二大多少？

答案原来是一个总的 N-1 +天花板（log n）的 - 1 比较，其中对数是底座2还可以证明使用对抗性的论点，即它不可能在最坏的情况下做比这更好。

其他提示

编辑：哎呀，由于愚蠢而错过了一件简单的事情。这个解决方案是不正确的，尽管我将其保留在这里，因为它仍然是 avg(n+log(n))。感谢 ShreevatsaR 指出我的愚蠢。我确实考虑过树搜索，但完全错过了回溯以找到 log(n) 中第二大数字的想法。

无论如何，下面是我的证明，证明为什么较差的算法不超过 avg(n+log(n))。在现实生活中，它至少应该表现得很好。

  • 首先与第二高记录数字进行比较。
  • 仅当比较成功时，才与最高记录数进行比较。

为了证明平均是 n+log n，我们只需证明第一次比较平均只成功 log(n) 次。这很容易看到或演示。

  1. 假设 P 是列表的排序版本中当前第二大数字的实际位置，并运行算法
  2. 如果P>2，那么当找到更大的数时，新的P平均不会超过P/2。
  3. 如果P=2，则第一次比较不会成功，因为没有数字大于当前第二大数字。
  4. P最多可以等于N
  5. 从 2、3 和 4 可以看出，第一次比较平均成功次数不会超过 log(N) 次。

这样如何：

for each listOfNumbers as number
    if number > secondHighest
        if number > highest
            secondHighest = highest
            highest = number
        else
            secondHighest = number

张贴由ShreevatsaR答案似乎是为O（n log n）的

第一遍（n个操作）产生N / 2的答案。通过重复，我想你的意思是你会做N / 2的操作，得到N / 4的答案。你会去通过循环日志n次。这是很多像合并排序，除了合并排序始终处理n至每一次节点。它还可以运行循环日志n次。我没有看到这个算法将如何跟踪第二higest数量。

nickf具有正确的答案。最坏的情况是，当列表进行排序，它会做2n个比较 - 这是O（n）

顺便说一句，为O（n + log n）的是O（n）的数量级次指最坏的情况下渐进增长。

可以使用计数排序，基数排序，桶排序或其他线性时间算法首先降序排序的列表中。然后，只需获得排序列表的前2个元素。 因此，这将需要（N）+ 2 =（n）的

请注意，该算法可以在线性时间排序，因为每一个都有其自己的假设。

伪代码（不是本实质上N 2）

int highestNum = 0
int secondHighest = highestNum

for(i = 0; i < list.length; i++)
{
if(list[i] >= highestNum)
{
secondHighest = highestNum
highestNum = list[i]
}
}
许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top