我们如何有效地从数组中找到第二个最大值？

Question

是否可以通过仅遍历整数数组从整数数组中找到第二个最大数字？

例如，我有一个由五个整数组成的数组，我想从中找到第二个最大数字。这是我在采访中进行的尝试：

#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};，这阻止了它if第二次进入条件。我对面试官说，唯一的方法是将数组解析两次（两个for循环）。有人有更好的解决方案吗？

Answer 1

你的初始化max和second_max对-1有缺陷。如果数组具有类似的值{-2,-3,-4}怎么办？

相反，您可以做的是获取数组的前2个元素（假设数组至少包含2个元素），将它们进行比较，将较小的一个分配给second_max，将较大的一个分配给max：

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

然后从第三个元素开始进行比较，max并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];
    }
}