O(n)时间复杂度查找数组第二大元素
2024-08-24 05:06:27
分析：要求O(n)时间复杂度，不能用排序。可以设置两个临时变量分别保存当前最大值以及当前第二大的值，然后遍历数组，不断更新最大值和第二大的数值。
代码：
bool findSec(vector<int> num, int &secv)
{
if (num.size()<)
{
return false;
} int maxv=num[];
secv=num[];
int temp=; for (int i=;i<(int)num.size();i++)
{
if (num[i]>maxv)
{
temp=maxv;
maxv=num[i];
if (temp>secv)
{
secv=temp;
}
}
else if(num[i]<maxv&&num[i]>secv)//num[i]<maxv这条判断不可少，否则最大元素重复时返回出错;
{
secv=num[i];
} }
return true;
}
参考此文将代码稍作修改：
bool findSec(vector<int> num, int &secv)
{
if (num.size()<)
{
return false;
} int maxv=num[];
secv=num[]; if (secv>maxv)
{
swap(secv,maxv);
} for (int i=;i<(int)num.size();i++)
{
if (num[i]>maxv)
{
secv=maxv;
maxv=num[i];
}
else if (num[i]<maxv&&num[i]>secv)//num[i]<maxv这条判断不可少，否则最大元素重复时返回出错;
{
secv=num[i];
}
} return true;
}
最新文章
- Lightbox改造——支持滚轮缩放
- excel 两列比较内容是否相同
- javascript--Function
- css 射线实现方法
- C#整理1——进制转换
- meta标签有何作用？一起来学习一下
- windows的三种内存管理方法
- Android源码浅析（三）——Android AOSP 5.1.1源码的同步sync和编译make，搭建Samba服务器进行更便捷的烧录刷机
- Javascript高级编程学习笔记（1）—— JS简介
- 利用window.name+iframe跨域获取接口数据
- 单片机课程设计——课程设计之四位加法计算器（2）（C代码）
- 使用mysqldump以分隔文本格式转储数据
- go test :Wrong test signature
- openstack--部暑
- npm包开发（whale-makelink）
- public private protected extends
- cordova 源码分析记录
- go语言之进阶篇通过switch实现类型断言
- ODBC的基础架构
- MySQL学习笔记：exists和in的区别