|簡體中文

比思論壇

 找回密碼
 按這成為會員
搜索



查看: 444|回復: 0
打印 上一主題 下一主題

2.10 用最少次数寻找数组中的最大值和最小值[find min max of array]

[複製鏈接]

56

主題

0

好友

490

積分

中學生

Rank: 3Rank: 3

  • TA的每日心情

    6 天前
  • 簽到天數: 204 天

    [LV.7]常住居民III

    推廣值
    0
    貢獻值
    0
    金錢
    156
    威望
    490
    主題
    56
    樓主
    發表於 2014-7-18 20:48:23
    【题目】
    对于一个由N个整数组成的数组,需要比较多少次才能把最大和最小的数找出来呢?
    【分析】
    1. 遍历两次数组,分别找出最大值和最小值,需要进行 2N 次比较。
    2. 将数组中的元素分组,按顺序将数组中相邻的两个数分在同一组,用Max和Min来存储最大值和最小值。同一组比较完之后,较小的数与当前的最小值比较,如该数小于当前最小值,更新Min;较大的数与当前的最大值比较,若该数大于当前最大值,更新Max。Max初始化为数组前两个数中较大值,Min初始化为数组前两个组中较小值。这种方法的比较次数是(N/2)*3=1.5N次。
    C++ Code
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56

    /*
        version: 1.0
        author: hellogiser
        blog: http://www.cnblogs.com/hellogiser
        date: 2014/7/10
    */


    void getMinMax(int a, int b, int *min, int *max)
    {
        // compare 1 time
        if(a > b)
        {
            *min = b;
            *max = a;
        }
        else
        {
            *min = a;
            *max = b;
        }
    }

    void findArrMinMax(int a[], int size, int *min, int *max)
    {
        if(size == 0)
            return;
        if(size == 1)
        {
            *min = *max = a[0];
            return;
        }
        // get min max of a[0] a[1]
        getMinMax(a[0], a[1], min, max);

        int i, j;
        int *tempmin, *tempmax;
        for(i = 2, j = 3; i < size, j < size; i += 2, j += 2)
        {
            // get min max of a a[j]
            getMinMax(a, a[j], tempmin, tempmax);

            if(*tempmax > *max)
                *max = *tempmax;
            if(*tempmin < *min)
                *min = *tempmin;
        }

        // if array size is odd, then the last element a[size-1] is not contained in previous steps,so compare here
        if(size % 2 != 0)
        {
            if(a[size - 1] > *max)
                *max = a[size - 1];
            else if(a[size - 1] < *min)
                *min = a[size - 1];
        }
    }

    3. 使用分治法,在N个数中求最小值Min和最大值Max,我们只需要求出前后N/2个数的Min和Max,然后取较小的Min和较大的Max即可。设比较的次数为T(n),那么T(n)=2T(n/2)+2,T(1)=0,T(2)=1,这种方法的比较次数是1.5N-2次。
    C++ Code
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33

    /*
        version: 1.0
        author: hellogiser
        blog: http://www.cnblogs.com/hellogiser
        date: 2014/7/10
    */


    void findArrMinMax(int a[], int begin, int end, int *min, int *max)
    {
        if(end - begin <= 1)
        {
            if(a[end] > a[begin])
            {
                *max = a[end];
                *min = a[begin];
            }
            else
            {
                *max = a[begin];
                *min = a[end];
            }
            return;
        }

        int maxL, maxR;
        int minL, minR;
        int mid = begin + (end - begin) / 2;
        findArrMinMax(a, begin, mid, &minL, &maxL);
        findArrMinMax(a, mid + 1, end, &minR, &maxR);
        *min = minL > minR ? minR : minL;
        *max = maxL > maxR ? maxL : maxR;
    }


    重要聲明:本論壇是以即時上載留言的方式運作,比思論壇對所有留言的真實性、完整性及立場等,不負任何法律責任。而一切留言之言論只代表留言者個人意見,並非本網站之立場,讀者及用戶不應信賴內容,並應自行判斷內容之真實性。於有關情形下,讀者及用戶應尋求專業意見(如涉及醫療、法律或投資等問題)。 由於本論壇受到「即時上載留言」運作方式所規限,故不能完全監察所有留言,若讀者及用戶發現有留言出現問題,請聯絡我們比思論壇有權刪除任何留言及拒絕任何人士上載留言 (刪除前或不會作事先警告及通知 ),同時亦有不刪除留言的權利,如有任何爭議,管理員擁有最終的詮釋權。用戶切勿撰寫粗言穢語、誹謗、渲染色情暴力或人身攻擊的言論,敬請自律。本網站保留一切法律權利。

    手機版| 廣告聯繫

    GMT+8, 2024-11-1 07:30 , Processed in 0.045356 second(s), 25 queries , Gzip On.

    Powered by Discuz! X2.5

    © 2001-2012 Comsenz Inc.

    回頂部