作者cocoyan (抠抠厌)
看板Prob_Solve
标题Re: [问题] 用最少比较次数找最大、最小等值
时间Mon Jul 4 03:52:28 2016
※ 引述《lionhome20 (林北大GG)》之铭言：
: 各位神人好
: 想请问在int array[5000]里
: 如何用最少的compare次数
: 找出最大 最小 次大 次小的值
: 有没有小於下列5000*4次 compare的找法
: (找每一个数都用暴力法)
: for(i=0;i<5000;i++)
: if(array[i] > Max)
: Max = array[i]
: 感谢
int Max;
int Max2;
int Min;
int Min2;
if(array[0]>array[1])
{
Max=array[0];
Max2=array[1];
Min=array[1];
Min2=array[0];
}
else
{
Max=array[1];
Max2=array[0];
Min=array[0];
Max2=array[1];
}
for(i=2;i<5000;i++)
{
if(array[i]>Max)
{
Max=array[i];
Max2=Max;
}
if(array[i]<Min)
{
Min=array[i];
Min2=Min;
}
}
应该是9997次比较
有误请指正
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 140.112.230.110
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1467575552.A.898.html
1F：→ s89162504: O(n) ... 07/04 04:34
2F：→ yr: XD 07/04 09:48
3F：推 arethusa99: 看起来应该可以更少 array[i]>max 跟array[i]<min 07/04 09:55
4F：→ arethusa99: 应该不会同时发生 所以改用else if 会不会更少一点啊 07/04 09:55
5F：→ arethusa99: 虽然说 这样我就不会算次数了QQ 07/04 09:55
6F：推 yvb: 程式概念是对的,但细节是错的,可能无法得到正确答案. 07/04 14:22
7F：→ yvb: 1. for中两个if内的式子,将导致Max和Max2相同,同理Min和Min2. 07/04 14:31
8F：→ yvb: 2. for的if,应跟次大或次小比,不然a[i]若介於最大和次大间... 07/04 14:33
9F：→ yvb: 3. 由2. 因为要和次大次小比,无法改成else if. 07/04 14:34
10F：推 arethusa99: QQ 楼上是对的 我没注意到这细节 07/04 20:56