问一个编程算法的问题,一堆无序数,如何从里面取出第二个大的数?

RTRT
并且要用最小的系统开销

3 个回答

一直取最大的两个数,要遍历整张表,复杂度 2*n?

遍历啊……取两个变量存结果MAX1,MAX2
从无序数中预读一个数a存入MAX1
后面开始遍历剩余数n,若n>MAX1 则MAX2=MAX1,MAX1=n;否则直接处理下一个数。

遍历完成,MAX1就是最大的数,那MAX2当然就是第二大的数了。
总共进行了n-1次判断。


发现该算法有缺陷……当第二大的数字序列在最大的数字后面时,无法得出正确结果……
设变量MAX1,MAX2,共有n个元素
读取两个元素,并比较,大的赋值MAX1,小的赋值MAX2。
遍历剩下n-2个元素,取a
If (a>MAX1) then
MAX2=MAX1
MAX1=a
elseif (a>MAX2)
MAX2=a
End if
最后进行了2n-1次比较。

Image我来画个图
采用淘汰赛制可以减少需要比较的次数
可以单线程也可以用多线程加速运算,资源可以继续优化
遍历比较的资源消耗少,运算虽然多,但是考虑到只需要使用寄存器,可能还是最优解

你的回答