算法设计-找第二大数（C++)

一、问题描述

用于在给定的整数数组中找到 第二大值。

二、详细代码

#include<iostream>
#include<limits.h>
using namespace std;
//初始化最大值为a[0]，次大值为a[1]，遍历一次，每次比较并更新最大值和次大值，最后就可以得到次大值
//参数：数组地址，数组size
int find_second_maxValue(int *a,int size)
{if(size<2)return a[0];int max=a[0];  //最大值int second=INT_MIN;  //第二大值for(int i=0;i<size;i++){if(a[i]>max){second=max;   //更新最大值和次大值max=a[i];}else if(a[i]<max && a[i]>second){second=a[i];}}return second;
}
int main()
{int array[5]={11,22,99,77,44};int second=find_second_maxValue(array,sizeof(array)/sizeof(array[0]));cout<<"第二大数：  "<<second<<endl;return 0;
}

三、详细阐述

• find_second_maxValue 函数用于在数组中找到第二大值。

参数

• int *a：数组的起始地址。

• int size：数组的大小。

变量

• max：存储当前遍历到的最大值，初始值为数组的第一个元素 a[0]。

• second：存储当前遍历到的第二大值，初始值为 INT_MIN（即最小整数值）。

算法步骤

1. 边界检查：

   • 如果数组大小小于 2，直接返回数组的第一个元素 a[0]，因为数组中没有足够的元素来定义第二大值。

2. 遍历数组：

   • 遍历数组中的每个元素 a[i]。

   • 如果当前元素 a[i] 大于 max：

     • 将 max 的值赋给 second（因为原来的最大值变成了第二大值）。

     • 将 a[i] 赋给 max（更新最大值）。

   • 如果当前元素 a[i] 小于 max 但大于 second：

     • 将 a[i] 赋给 second（更新第二大值）。

3. 返回结果：

   • 返回 second，即数组中的第二大值。

四、复杂度

• 时间复杂度为 O(n)，空间复杂度为 O(1)。