我们如何才能找到从阵列有效次大？ [英] How can we find second maximum from array efficiently?

问题描述

是否有可能通过遍历数组一次发现从整型数组第二最大值是多少？

Is it possible to find the second maximum number from an array of integers by traversing the array only once?

作为一个例子，我有五个整数，我想找到第二个最大数量的数组。这是我给在采访中，企图：

As an example, I have a array of five integers from which I want to find second maximum number. Here is an attempt I gave in the interview:

#define MIN -1
int main()
{
    int max=MIN,second_max=MIN;
    int arr[6]={0,1,2,3,4,5};
    for(int i=0;i<5;i++){
        cout<<"::"<<arr[i];
    }
    for(int i=0;i<5;i++){
        if(arr[i]>max){
            second_max=max;
            max=arr[i];          
        }
    }
    cout<<endl<<"Second Max:"<<second_max;
    int i;
    cin>>i;
    return 0;
}

面试官，但是，想出了测试用例 INT ARR [6] = {5,4,3,2,1,0}; ，其中$ p $从去到如果情况的第二次pvents它。 我对采访者说，唯一的办法是将解析阵列的两倍（两个为循环）。没有任何人有一个更好的解决方案？

The interviewer, however, came up with the test case int arr[6]={5,4,3,2,1,0};, which prevents it from going to the if condition the second time. I said to the interviewer that the only way would be to parse the array two times (two for loops). Does anybody have a better solution?

推荐答案

您初始化最大的和 second_max 来 1 是有缺陷的。如果有什么数组有值，例如？{ - 2，-3，-4}

Your initialization of max and second_max to -1 is flawed. What if the array has values like {-2,-3,-4}?

你可以做的反而是把数组的第2个元素（假设数组有至少2元），对它们进行比较，指定更小的一个 second_max 和较大的一个，以最高：

What you can do instead is to take the first 2 elements of the array (assuming the array has at least 2 elements), compare them, assign the smaller one to second_max and the larger one to max:

if(arr[0] > arr[1]) {
 second_max = arr[1];
 max = arr[0];
} else {
 second_max = arr[0];
 max = arr[1];
}

然后开始从3元和更新比较最高和/或 second_max 需要：

for(int i = 2; i < arr_len; i++){
    // use >= n not just > as max and second_max can hav same value. Ex:{1,2,3,3}   
    if(arr[i] >= max){  
        second_max=max;
        max=arr[i];          
    }
    else if(arr[i] > second_max){
        second_max=arr[i];
    }
}

这篇关于我们如何才能找到从阵列有效次大？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！