Re: [問題] 用最少比較次數找最大、最小等值

[cocoyan (摳摳厭)]

※ 引述《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://www.ptt.cc/bbs/Prob_Solve/M.1467575552.A.898.html
→ s89162504: O(n) ...
→ yr: XD
推 arethusa99: 看起來應該可以更少 array[i]>max 跟array[i]<min
→ arethusa99: 應該不會同時發生 所以改用else if 會不會更少一點啊
→ arethusa99: 雖然說 這樣我就不會算次數了QQ
推 yvb: 程式概念是對的,但細節是錯的,可能無法得到正確答案.
→ yvb: 1. for中兩個if內的式子,將導致Max和Max2相同,同理Min和Min2.
→ yvb: 2. for的if,應跟次大或次小比,不然a[i]若介於最大和次大間...
→ yvb: 3. 由2. 因為要和次大次小比,無法改成else if.
推 arethusa99: QQ 樓上是對的 我沒注意到這細節