极客教程C语言程序 数组的最大值和最小值的
给出一个大小为N的数组，任务是用最少的比较次数找到数组的最大和最小元素。
示例s:
输入： arr[] = {3, 5, 4, 1, 9}。
输出： 最小的元素是。1
最大的元素是。9
输入： arr[] = {22, 14, 8, 17, 35, 3}
输出： 最小的元素是。3
最大的元素是。35
首先，我们如何从一个函数中返回多个值？我们可以使用结构或指针来实现。
我们创建了一个名为pair的结构（其中包含min和max）来返回多个值。
struct pair {
int min;
int max;
};
用线性搜索法计算数组的最大值和最小值
初始化min和max的值，分别为前两个元素的最小值和最大值。从第3个开始，将每个元素与max和min进行比较，并相应地改变max和min（即，如果元素小于min，则改变min，否则如果元素大于max，则改变max，否则忽略该元素）。
下面是上述方法的实现。
/* structure is used to return two values from minMax() */
#include<stdio.h>
struct pair
{
int min;
int max;
};
struct pair getMinMax(int arr[], int n)
{
struct pair minmax;
int i;
/*If there is only one element then return it as min and max both*/
if (n == 1)
{
minmax.max = arr[0];
minmax.min = arr[0];
return minmax;
}
/* If there are more than one elements, then initialize min
and max*/
if (arr[0] > arr[1])
{
minmax.max = arr[0];
minmax.min = arr[1];
}
else
{
minmax.max = arr[1];
minmax.min = arr[0];
}
for (i = 2; i<n; i++)
{
if (arr[i] > minmax.max)
minmax.max = arr[i];
else if (arr[i] < minmax.min)
minmax.min = arr[i];
}
return minmax;
}
/* Driver program to test above function */
int main()
{
int arr[] = {1000, 11, 445, 1, 330, 3000};
int arr_size = 6;
struct pair minmax = getMinMax (arr, arr_size);
printf("nMinimum element is %d", minmax.min);
printf("nMaximum element is %d", minmax.max);
getchar();
}
输出:
Minimum element is 1
Maximum element is 3000
时间复杂度： O(n)
辅助空间： 因为不需要额外的空间，所以是O(1)。
在这种方法中，最坏的情况下比较总数为1+2(n-2)，最好的情况下为1+n – 2。
在上述实现中，最坏的情况发生在元素按降序排序的时候，最好的情况发生在元素按升序排序的时候。
使用锦标赛的方法，实现数组的最大和最小
将数组分成两部分，比较两部分的最大值和最小值，得到整个数组的最大值和最小值。
Pair MaxMin(array, array_size)
如果array_size = 1
返回元素的最大值和最小值
否则，如果arry_size = 2
进行一次比较来确定最大和最小
返回这一对
否则 /* array_size > 2 */
递归左半部分的最大和最小值
循环寻找右半部分的最大和最小值
通过一次比较确定两个候选数的真正最大值
进行一次比较，确定两个候选数的真正最小值
返回一对最大值和最小值
下面是上述方法的实现。
/* structure is used to return two values from minMax() */
#include <stdio.h>
struct pair {
int min;
int max;
};
struct pair getMinMax(int arr[], int low, int high)
{
struct pair minmax, mml, mmr;
int mid;
// If there is only one element
if (low == high) {
minmax.max = arr[low];
minmax.min = arr[low];
return minmax;
}
/* If there are two elements */
if (high == low + 1) {
if (arr[low] > arr[high]) {
minmax.max = arr[low];
minmax.min = arr[high];
}
else {
minmax.max = arr[high];
minmax.min = arr[low];
}
return minmax;
}
/* If there are more than 2 elements */
mid = (low + high) / 2;
mml = getMinMax(arr, low, mid);
mmr = getMinMax(arr, mid + 1, high);
/* compare minimums of two parts*/
if (mml.min < mmr.min)
minmax.min = mml.min;
else
minmax.min = mmr.min;
/* compare maximums of two parts*/
if (mml.max > mmr.max)
minmax.max = mml.max;
else
minmax.max = mmr.max;
return minmax;
}
/* Driver program to test above function */
int main()
{
int arr[] = { 1000, 11, 445, 1, 330, 3000 };
int arr_size = 6;
struct pair minmax = getMinMax(arr, 0, arr_size - 1);
printf("nMinimum element is %d", minmax.min);
printf("nMaximum element is %d", minmax.max);
getchar();
}
输出
Minimum element is 1
Maximum element is 3000
时间复杂度： O(n)
辅助空间： O(log n)，因为在递归调用过程中形成的树的最大高度的堆栈空间将被填充，与二叉树相同。
总的比较次数：设比较次数为T(n)。T(n)可以写成如下。
算法范式：分而治之
T(n) = T(floor(n/2)) + T(ceil(n/2)) + 2
T(2) = 1
T(1) = 0
如果n是2的幂，那么我们可以把T(n)写成。
T(n) = 2T(n/2) + 2
在解决了上述递归后，我们得到
T(n) = 3n/2 -2
因此，如果n是2的幂，该方法会进行3n/2-2的比较，而如果n不是2的幂，则会进行超过3n/2-2的比较。
通过成对比较实现数组的最大和最小
如果n是奇数，那么初始化min和max为第一个元素。
如果n是偶数，则将min和max分别初始化为前两个元素的最小和最大。
对于其余的元素，成对挑选，并分别用最大和最小值比较它们的最大和最小值。
下面是上述方法的实现。
#include<stdio.h>
/* structure is used to return two values from minMax() */
struct pair
{
int min;
int max;
};
struct pair getMinMax(int arr[], int n)
{
struct pair minmax;
int i;
/* If array has even number of elements then
initialize the first two elements as minimum and
maximum */
if (n%2 == 0)
{
if (arr[0] > arr[1])
{
minmax.max = arr[0];
minmax.min = arr[1];
}
else
{
minmax.min = arr[0];
minmax.max = arr[1];
}
i = 2; /* set the starting index for loop */
}
/* If array has odd number of elements then
initialize the first element as minimum and
maximum */
else
{
minmax.min = arr[0];
minmax.max = arr[0];
i = 1; /* set the starting index for loop */
}
/* In the while loop, pick elements in pair and
compare the pair with max and min so far */
while (i < n-1)
{
if (arr[i] > arr[i+1])
{
if(arr[i] > minmax.max)
minmax.max = arr[i];
if(arr[i+1] < minmax.min)
minmax.min = arr[i+1];
}
else
{
if (arr[i+1] > minmax.max)
minmax.max = arr[i+1];
if (arr[i] < minmax.min)
minmax.min = arr[i];
}
i += 2; /* Increment the index by 2 as two
elements are processed in loop */
}
return minmax;
}
/* Driver program to test above function */
int main()
{
int arr[] = {1000, 11, 445, 1, 330, 3000};
int arr_size = 6;
struct pair minmax = getMinMax (arr, arr_size);
printf("nMinimum element is %d", minmax.min);
printf("nMaximum element is %d", minmax.max);
getchar();
}
输出:
Minimum element is 1
Maximum element is 3000
时间复杂度： O(n)
辅助性 因为不需要额外的空间，所以是O(1)。
比较的总数。偶数和奇数的n不同，见下文。
If n is odd: 3*(n-1)/2
If n is even: 1 Initial comparison for initializing min and max,
and 3(n-2)/2 comparisons for rest of the elements
= 1 + 3*(n-2)/2 = 3n/2 -2
当n是2的幂时，第二和第三种方法进行的比较次数相等。
一般来说，方法3似乎是最好的。