采访算法:找到大小为n的数组中的两个最大元素

Question

这是我在网上看到的一个面试问题,我不确定我是否有正确的想法.

问题出在这里:

设计一种算法来查找n个数字序列中的两个最大元素.比较次数需要为n + O(log n)

我想我可以选择快速排序并在找到两个最大的元素时停止？但不是100%肯定它.任何人都有想法请分享

Answer 1

递归地拆分数组,找到每一半中最大的元素,然后找到最大元素与之比较的最大元素.第一部分需要n比较,最后部分需要O(log n).这是一个例子:

1 2 5 4 9 7 8 7 5 4 1 0 1 4 2 3
2   5   9   8   5   1   4   3
5       9       5       4
9               5
9

在每一步,我正在合并相邻的数字并取两者中的较大者.它需要n比较才能得到最大的数字9.然后,如果我们看一下9被比较的每个数字(5,5,8,7),我们看到最大的数字是8,这必须是数组中的第二大.由于此处有O(log n)级别,因此需要进行O(log n)比较.