首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >查找数组中比较次数最少的第二大元素

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

Stack Overflow用户
提问于 2010-09-02 23:39:39
回答 22查看 131.8K关注 0票数 72

对于大小为N的数组,需要多少次比较?

EN

回答 22

Stack Overflow用户

回答已采纳

发布于 2010-09-02 23:47:14

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

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

代码语言:javascript
复制
   |
  / \
 |   |
/ \ / \
x x x x

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

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

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

票数 123
EN

Stack Overflow用户

发布于 2013-08-07 11:07:39

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

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

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

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

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

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

票数 10
EN

Stack Overflow用户

发布于 2010-09-03 00:09:27

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

代码语言:javascript
复制
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个元素中的一个是数组中最小的)。

票数 2
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/3628718

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档