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

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];
}

然后从第3个元素开始比较并更新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];
    }
}

Answer 2

最简单的解决方案是使用std::nth_element.

Answer 3

你需要第二次测试:

 for(int i=0;i<5;i++){  
   if(arr[i]>max){  
     second_max=max;  
     max=arr[i];            
   }
   else if (arr[i] > second_max && arr[i] != max){
     second_max = arr[i];
   }
 }