问查找数组中比较次数最少的第二大元素

EN

最优算法使用n+log n-2比较。将元素视为竞争对手，而锦标赛将对它们进行排名。

首先，比较元素，如在树中

   |
  / \
 |   |
/ \ / \
x x x x

这需要n-1次比较，并且每个元素最多涉及到log次比较。您将找到最大的元素作为获胜者。

第二大元素一定输给了胜利者(他不可能输给不同的元素)，所以他是胜利者所对抗的log元素之一。您可以使用log 1比较找到它们中的哪一个。

通过对抗性论证证明了最优性。请参见https://math.stackexchange.com/questions/1601、http://compgeom.cs.uiuc.edu/~jeffe/teaching/497/02-selection.pdf、http://www.imada.sdu.dk/~jbj/DM19/lb06.pdf或https://www.utdallas.edu/~chandra/documents/6363/lbd.pdf

使用冒泡排序或选择排序算法，按降序对数组进行排序。不要对数组进行完全排序。只有两次传球。第一遍给出了最大的元素，第二遍给出了第二大元素。

不是的。第一次通过的比较数: n-1

不是的。第一次通过的比较数: n-2

总共没有。寻找第二大的比较: 2n-3

也许你可以推广这个算法。如果你需要第三个最大的，那么你可以通过3次。

通过以上策略，您不需要任何临时变量，因为冒泡排序和选择排序都是in place sorting算法。

下面是一些可能不是最优的代码，但至少找到了第二大元素：

if( val[ 0 ] > val[ 1 ] )
{
    largest = val[ 0 ]
    secondLargest = val[ 1 ];
}
else
{
    largest = val[ 1 ]
    secondLargest = val[ 0 ];
}

for( i = 2; i < N; ++i )
{
    if( val[ i ] > secondLargest )
    {
        if( val[ i ] > largest )
        {
            secondLargest = largest;
            largest = val[ i ];
        }
        else
        {
            secondLargest = val[ i ];
        }
    }
}

如果最大的2个元素在数组的开头，则需要至少N-1个比较，在最坏的情况下最多需要2N-3个(前2个元素中的一个是数组中最小的)。