请问如何找无序数组里第2大的数 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

请问如何找无序数组里第2大的数

请问如何找无序数组里第2大的数# JobHunting - 待字闺中

c*z2014-09-02 07:09

1 楼

time O(n),大牛来写个简单的版本，看了些版本，比较杂

A*i2014-09-02 07:09

2 楼

先找出第一大的标记出来然后再遍历一遍跳过第一大就能找到第二大了

m*a2014-09-02 07:09

3 楼

你把数组撸两遍不就行了么？？

e*i2014-09-02 07:09

4 楼

size为2的堆。。。

【在 c**z 的大作中提到】

: time O(n),大牛来写个简单的版本，看了些版本，比较杂

y*i2014-09-02 07:09

5 楼

维护最大和次大2个变量，遍历一遍，不行吗？其实就是size为2的堆

q*c2014-09-02 07:09

6 楼

One pass:
int find2ndLargest(int A[], int n)
{
int first = INT_MIN, second = INT_MIN;
for(int i = 0; i < n; ++i) {
if(A[i] > first) {
first = A[i];
second = first;
}
else if(A[i] > second && A[i] < first)
second = A[i];
}
return second;
}

【在 c**z 的大作中提到】

: time O(n),大牛来写个简单的版本，看了些版本，比较杂

e*i2014-09-02 07:09

7 楼

second first次序错了。。。
都是A[i]了
这个是第二大的值，不确定是不是第二大的数嗯，不过这个无伤

【在 q********c 的大作中提到】

: One pass:
: int find2ndLargest(int A[], int n)
: {
: int first = INT_MIN, second = INT_MIN;
: for(int i = 0; i < n; ++i) {
: if(A[i] > first) {
: first = A[i];
: second = first;
: }
: else if(A[i] > second && A[i] < first)

c*z2014-09-02 07:09

8 楼

第二大的值和第二大的数有撒区别

【在 e*****i 的大作中提到】

: second first次序错了。。。
: 都是A[i]了
: 这个是第二大的值，不确定是不是第二大的数嗯，不过这个无伤

e*i2014-09-02 07:09

9 楼

两个8一个7，大概就是这个意思，不要揪我语文不好哈哈哈~

【在 c**z 的大作中提到】

: 第二大的值和第二大的数有撒区别

c*z2014-09-02 07:09

10 楼

有dup怎么处理？

【在 e*****i 的大作中提到】

: second first次序错了。。。
: 都是A[i]了
: 这个是第二大的值，不确定是不是第二大的数嗯，不过这个无伤