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

Question

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

algorithmcomputer-science

5

我正在尝试找出一种算法，以查找数字列表中最高的两个数字。

最高的数字可以在n-1个阶段中找到，可能是通过冒泡排序的第一步或类似方法完成。对我而言，似乎在总共1.5n次比较中也可以找到下一个最高的数字。

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

编辑：当我说n + log（n）时，我不是指O（n + log n），而是确切地n + log n。

- Meir

请参见问题编号1602998。 - Niels Castle

2

这是一个方便的链接：https://dev59.com/NXI-5IYBdhLWcg3w8dUQ - nickf

数字必须不同吗？例如，在列表（1、3、2、3）中，最高的两个数字是（3、3）还是（2、3）？ - user159335

@Niels，我刚刚仔细查看了那个问题和答案，但是我没有看到任何可以帮助我实现n + log n结果的东西。你能具体一点吗？ - Meir

这项作业还需要交吗？我可以更清楚地解释答案，但我不想全部都透露出来... :) - ShreevatsaR

显示剩余2条评论

6个回答

2

编辑：糊涂大意地错过了一个简单的事情。这个解决方案是不正确的，尽管我仍然保留它，因为它仍然是avg(n+log(n))。感谢ShreevatsaR指出我的愚蠢。我确实考虑了树搜索，但完全忽略了回溯查找第二高的数字的想法，以log(n)的时间复杂度。

无论如何，以下是我证明这个劣质算法不超过平均n+log n的原因。在现实生活中，它应该仍然表现得相当好。

首先与第二高记录数进行比较。
只有在该比较成功的情况下，才与最高记录数进行比较。

为了证明它的平均值为n+log n，我们只需证明第一次比较平均只成功了log(n)次。这是相当容易看到或证明的。

假设P是列表排序后当前第二大数字的实际位置，并运行算法
如果P>2，则当发现更大的数字时，新的P平均不会超过P/2。
如果P=2，则第一次比较不能成功，因为没有数字大于当前第二大的数字。
P最多可以等于N
从2、3和4中，应该很容易看出第一次比较平均不能成功超过log(N)次。

- Marcus Andrén

1

你的前几行不正确：在最坏情况下，你不需要进行 2*n 次比较。实际上它可以用 (n-1)+ceiling(log n)-1 次精确比较来完成，正如问题所要求的。我不会给这个回答点踩，因为其余部分是正确的，但“我想不出方法”并不能作为证明。 :P - ShreevatsaR

0

这样怎么样：

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

- nickf

1

这需要O(2n)个比较，这比O(n+log(n))要大。 - Dominic Rodger

以上是指最坏情况下的运行时间，如果数字按升序存储。 - Dominic Rodger

4

O(2n)和O(n)是一样的，所以那个评论没有意义。 - user181548

是的。循环只进行一次，它将在(1 + 2/n)比较和2n之间的某个位置，具体取决于初始顺序。有更好的想法吗？ - nickf

1

@Kinopiko，抱歉，我有点脑残。忽略 O，希望我的评论有意义。（即 2n 次比较比 n + log(n) 次比较更多） - Dominic Rodger

0

伪代码（这不基本上就是n吗？）

int highestNum = 0
int secondHighest = highestNum

for(i = 0; i < list.length; i++)
{
if(list[i] >= highestNum)
{
secondHighest = highestNum
highestNum = list[i]
}
}

- Cobalt

1

在这个列表上进行测试：0 3 2 1。secondHighest将保持为0。（更一般地说，如果最高的数字出现在第二高的数字之前，您的代码将错过第二高的数字。） - ShreevatsaR

0

ShreevatsaR发布的答案似乎是O(n log n)。

第一次遍历（n个操作）会产生n/2个答案。通过重复，我猜你的意思是你将执行n/2个操作以产生n/4个答案。您将通过循环log n次。这很像归并排序，只是归并排序每次始终处理n个节点。它也运行循环log n次。我不明白这个算法如何跟踪第二高的数字。

nickf给出了正确的答案。最坏情况是列表已排序，它将进行2n次比较-即O(n)。

顺便说一句，O(n + log n)是O(n)，阶符号指最坏情况渐近增长。

- redcayuga

嗯？n/2 + n/4 + … = n-1。（另一种看法是：除了获胜者，每个人都只输了一次。）我给出的算法恰好需要n+log（n）-2次比较（不仅仅是渐近的）。请注意，所讨论的度量值是比较次数，而不是运行时间。（但是n+log（n）是O（n），所以运行时间也是O（n）。对于作业问题，很抱歉我的答案不够清晰，但我不想完全放弃答案。 - ShreevatsaR

0

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

请注意，这些算法可以在线性时间内进行排序，因为每个算法都有自己的假设条件。

- Enrique

(1) 给定的数字没有任何保证，因此无法进行线性时间排序。(2) 注意这里的度量是比较次数，而不是操作次数。(3) 请注意，它要求的是恰好 n+log(n)，而不是 O(n + log(n)) —— 后者只是 O(n)。 - ShreevatsaR

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ShreevatsaR · Accepted Answer

是的，最多只需要(n+log n)次比较就可以找出最大的数。但是如果我直接给你答案就不好了，让我试试怎么样解释吧！首先把n个数两两比较，选出ceil(n/2)个“赢家”再重复上述步骤，就像构建一棵二叉树。现在有几个问题：要找到最大值需要比较多少次呢？这些“赢家”分别赢得了多少次？第二大的数可能输给了谁？那么现在找出第二大的数需要比较多少次呢？答案是总共需要n-1+向上取整(log n)-1次比较，其中log以2为底。采用对手策略可以证明，在最坏情况下，没有比这更好的方法。