查找前三个最大或者前三个最小的数,相当于查找冠亚季前三名的算法了,应该如何做呢?
当然可以用堆做,时间效率很高,下面是个简易的方法。
查找前三个最大数算法:
1) 初始化三个数为INT_MIN
2) 循环
a) 如果当前元素大于第一名,更新第一名,且第三名=第二名; 第二名=第一名;
b) 如果当前元素大于第二名,而且不等于第一名,那么更新第二名,而第三名=第二名;
c) 如果当前元素大于第三名,而且不等于第二名,那么更新第三名。
程序:
#include<iostream>
#include<vector>
using namespace std;
struct TriInts
{
int champion;
int secd;
int thir;
};
void findFirstThreePlace(TriInts &thr, vector<int> &vArray)
{
thr.champion = INT_MIN;
thr.secd = INT_MIN;
thr.thir = INT_MIN;
if(vArray.empty()) return;
for (int i = 0; i < vArray.size(); i++)
{
if (vArray[i] > thr.champion)
{
thr.thir = thr.secd;
thr.secd = thr.champion;
thr.champion = vArray[i];
}
else if (vArray[i] > thr.secd && vArray[i] != thr.champion)
{
thr.thir = thr.secd;
thr.secd = vArray[i];
}
else if (vArray[i] > thr.thir && vArray[i] != thr.secd)
{
thr.thir = vArray[i];
}
}
}
int main()
{
int a[] = {2,5,7,9,3,11,20,13,16,38,29,22,13,68,55};
int az = sizeof(a) / sizeof(a[0]);
vector<int> vArr(a, a+az);
TriInts ti;
findFirstThreePlace(ti, vArr);
if(ti.champion == INT_MIN)
cout<<"There is not competition!\n";
else
cout<<"The champion is: "<<ti.champion<<endl;
if(ti.secd == INT_MIN)
cout<<"There not second place!\n";
else
cout<<"The second place is: "<<ti.secd<<endl;
if(ti.thir == INT_MIN)
cout<<"There not third place!\n";
else
cout<<"The third place is: "<<ti.thir<<endl;
system("pause");
return 0;
}
运行结果:
分享到:
相关推荐
* 时间复杂度按数量级递增排列依次为:常数阶 O(1)、对数阶 O(log2n)、线性阶 O(n)、线性对数阶 O(nlog2n)、平方阶 O(n^2)、立方阶 O(n^3)、…… k 次方阶 O(n^k)、指数阶 O(2^n)。 六、空间复杂度...
* 时间复杂度的分析:常数阶 O(1)、对数阶 O(log2n)、线性阶 O(n)、线性对数阶O(nlog2n)、平方阶 O(n^2)、立方阶 O(n^3)、…… k 次方阶 O(n^k)、指数阶 O(2^n)。 * 空间复杂度的分析:某个算法的...
在顺序表中实现的基本运算包括插入、删除等,平均时间复杂度均为O(n)。在链式存储结构中结点的逻辑顺序和物理顺序不一定相同,为了能对的表达结点间的逻辑关系,在存储每个结点值的同时,还存储了其后继结点的地址...
时间复杂度是某个算法的时间耗费,它是该算法所求解问题规模n的函数。渐近时间复杂度是指当问题规模趋向无穷大时,该算法时间复杂度的数量级。 线性表是数据结构中的一种基本结构。线性表的逻辑结构特征是很容易...
D. *建立函数create:根据一维数组a[n]建立一个单链表,使单链表中各元素的次序与a[n]中各元素的次序相同,要求该程序的时间复杂度为O(n)。 E. *整理函数tideup:在非递减有序的单链表中删除值相同的多余...
步骤3:如果X小于中间项的值,则在线性表的前半部分以二分法继续查找; 步骤4:如果X大于中间项的值,则在线性表的后半部分以二分法继续查找。 例如,长度为8的线性表关键码序列为:[6,13,27,30,38,46,47,70]...
取前五名的积分分别为:7、5、3、2、1,前三名的积分分别为:5、3、2;哪些取前五名或前三名由学生自己设定。(m=10 , w=8 , n=15) 功能要求: 1).可以输入各个项目的前三名或前五名的成绩; 2).能统计各学校总分...
(44) 对长度为N的线性表进行顺序查找,在最坏情况下所需要的比较次数为(B) 注:要牢记 A. N+1 B. N C. (N+1)/2 D. N/2 (45) 信息隐蔽的概念与下述哪一种概念直接相关(B) 注:P74 A.软件结构定义 B. 模块独立性 C. ...
答:n(n-1)/2#n*(n-1)/2#O(n(n-1)/2)#O(n*(n-1)/2) (13) 面向对象的程序设计方法中涉及的对象是系统中用来描述客观事物的一个______。 答:实体 (14) 软件的需求分析阶段的工作,可以概括为四个方面:______、需求...
3、 数据、结构、数据元素、算法(时间复杂度和空间复杂度) 二、 逻辑结构 1、 线性结构:有始有终,前后连接(称为前趋和后继) 2、 非线性结构:一个元素有多个前趋或后继 三、 数据的存储方法(物理结构):分为...
时间复杂度:数组插入删除 O(n),修改查找 O(1),所以数组适合查找修改;链表插入删除为 O(1),修改查找 O(n),链表更适合插入和删除。访问方式:数组支持随机访问,可以通过下标进行;链表不支持随机访问,必须从头...
并以量大低单价为产品主流,目前16位MCU与8位产品,还有相当幅度的价差,新的应用领域也仍在开发,业界预计,至少在2005年前8位的MCU仍是MCU产品的主流。 13. 学习ARM及嵌入式系统是否比学习其它一般单片机更有...
5.4 版本2:模拟BNF语法——复杂度O(N) 5.5 版本3:第一个复杂度O(log N)的优化 5.6 版本4:第二次优化:避免重复验证 5.7 版本5:第三次优化:复杂度 O(1) 5.8 版本 6:第四次优化:缓存(Caching) 5.9 从故事中学到...
本教程共分为5个部分,第一部分是C语言提高部分,第二部分为C++基础部分,第三部分为C++进阶部分,第四部分为C、C++及数据结构基础部分,第五部分为C_C++与设计模式基础,内容非常详细. 第一部分 C语言提高部分目录...
B:写出下列算法的时间复杂度和实现排序: (1)冒泡排序; (2)选择排序; (3)插入排序; (4)快速排序; (5)堆排序; (6)归并排序; 23、编写gbk_strlen函数,计算含有汉字的字符串的长度,汉字作为一个字符处理;已知...
而且我建议三名小组成 员最好是从大一一直打到大四的比赛,只有磨合默契的队友,才更有希望冲击国 奖甚至国一。 四、 数学建模竞赛比赛技巧 既然这是谈建模竞赛,那么我还是需要谈一谈应试技巧的话题,对于代做...