同时找最大最小值⌈3N/2⌉−2算法

ゝ一纸荒年。 2022-10-15 10:55 193阅读 0赞

同时找最大最小值  
题目定义：

> 给定一个大小为n的数组，无序，找到其中的最大值和最小值，要求元素间的比较次数尽可能少。

以下摘自《算法导论》：

事实上，我们只需要最多3⌊n/2⌋次比较就可以同时找到最小值和最大值。具体的方法是记录已知的最大值和最小值，然后对输入元素成对地进行处理。首先，我们将一对输入元素相互进行比较，然后把较小的与当前最小值进行比较，把较大的与当前最大值进行比较。这样，对每两个元素共需3次比较。

如何设定已知的最小值和最大值的初始值依赖于n是奇数还是偶数。如果n是奇数，我们就将最小值和最大值的初值都设为第一个元素的值，然后成对地处理余下的元素。如果n是偶数，就对前两个元素做一次比较，以决定最小值和最大值的初值，然后与n是奇数的情形一样，成对地处理余下的元素。

贴一下我的代码：

int min;
    int max;
    void findMinMax(int arr[], int n, int &min, int &max)
    { 
        int begin = 0;
        if (n % 2 == 1)
        { 
            min = max = arr[0];
            begin = 1;
        }
        else
        { 
            if (arr[0] < arr[1])
            { 
                min = arr[0];
                max = arr[1];
            } 
            else
            { 
                min = arr[1];
                max = arr[0];
            }
            begin = 2;
        }
    
        for (int i = begin; i < n-1; i = i+2)
        { 
            if (arr[i] < arr[i+1])
            { 
                if (arr[i] < min)
                    min = arr[i];
                if (arr[i+1] > max) 
                    max = arr[i+1];
            } 
            else
            { 
                if (arr[i+1] < min)
                    min = arr[i+1];
                if (arr[i] > max)
                    max = arr[i];
            }
        }
    }

NOIP2018普及组

给定一个含 N 个不相同数字的数组，在最坏情况下，找出其中最大或最小的数，至少需要 N−1 次比较操作。则最坏情况下，在该数组中同时找最大与最小的数至少需要（ ）次比较操作。（⌈⌉ 表示向上取整，⌊⌋表示向下取整）。  
A. 2N−2  
B. 2N−4  
C. ⌊3N/2⌋−2  
D. ⌈3N/2⌉−2  
在N 个不相同数字的数组同时查找最大值与最小值的算法思想如下：  
对N个数字两两比较，再将较大的数字与最大值打擂台，较小的数字与最小值打擂台。 最坏情况下的算法时间复杂度：

当N是奇数时，⌈N/2⌉×3 。将第一个数赋值给最大值和最小值。然后将剩下N−1个整数两两一组，共(N−1)/2组，每组组内比较一次，与最大值比较一次，与最小值比较一次，共三次。总比较次数：3×(N−1)/2。  
当N是偶数时，将前两个数比较一次，将较大数赋值给最大值、较小数赋值给最小值。然后将剩下的N−2个数两两一组，共(N−2)/2组，每组组内比较一次，与最大值比较一次，与最小值比较一次，共三次。总比较次数3×(N−2)/2+1。  
本题可以将尝试用N=3排除选项C，答案：D。