最大值和最小值

可以采用以下方法在o(n)时间内选出最大值。

图示:

    最大值和最小值

代码:

最大值和最小值
int Max(int *A, int arraysize)
{
        int max = A[0], i;
        for(i=0; i<arraysize; i++)
        {
            if(max < A[i])
            {
                max = A[i];
            }
        }
        return max;
}
//总共比较 n-1 次 
最大值和最小值

现在有两个问题:
1)如何同时找到最大值和最小值

  2)如何找到最大的两个值

解决方案:

问题1)

  方案一:可以采用像找最大值Max()函数解决。这样总共执行2(n-1)次

  方案二:一次处理两个元素,如下图所示:

          最大值和最小值

   分析:

     当数组元素总个数arraysize为奇数时,max和min同时赋值为第一个元素,之后的元素每两个比较一次之后大的和大的比,小的和小的比,总共比较(n-1)*3/2次。

  当arraysize为偶数时,头两个元素先比较一下,大的赋值给max,小的赋值给min,之后和上述一样,两个两个的处理。总共比较(n-2)*3/2+1次

显然2*n > 3/2 *n,所以方案二是一种更快的算法。

最大值和最小值
#include<stdio.h>
#include<stdlib.h>

int main()
{
        int max, min, i;
        int A[] = {0, 2, 55, 3, 5, 2, 9};
        int arraysize = 7;
        if(arraysize % 2 == 0)
        {
            if(A[0] > A[1])
            {
                max = A[0];
                min = A[1];
            }
            else
            {
                max = A[1];
                min = A[0];
            }
            i = 2;
        }
        else
        {
            max = min = A[0];
            i = 1;
        }
        for(; i<arraysize; i+=2)
        {
            if(A[i] > A[i+1])
            {
                if(A[i] > max)
                {
                    max = A[i];
                }
                if(A[i+1] <  min)
                {
                    min = A[i+1];
                }
            }
            else
            {
                if(A[i+1] > max)
                {
                    max = A[i+1];
                }
                if(A[i] < min)
                {
                    min = A[i];
                }
            }
        }
        printf("max:%d\nmin:%d\n", max, min);
        return 0;

}
最大值和最小值

 问题2)

  和问题1方案二一样,两个两个的处理。两个比较后大的和最大值比较,小的和次大值比较,如果大的就取代之。

 



本文转自jihite博客园博客,原文链接:http://www.cnblogs.com/kaituorensheng/archive/2013/03/03/2941951.html,如需转载请自行联系原作者