如何在只遍历一次整个数组的情况下找到一个整数数组中第二大的数?
例如,我有一个由五个整数组成的数组,我想找出其中第二大的数。以下是我在面试中尝试过的一种方法:
#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
循环)。有没有更好的解决方案?
堆
结构代替数组
或使用有序数组
结构。 - gaussblurinc