算法学习十五----找数组最大值和最小值

题目：给定一个数组，找出数组中的最大值和最小值

算法思路一：使用两个“游标”，p代表最大值，q代表最小值，初始为数组的第一个和第二个，不断向后移并且做比较，每次移动时将较大值与p比较，将p赋为较大值，较小值也同理。这样就能找到最大值和最小值。此算法要注意的地方就是当数组只有一个元素以及数组的个数为奇数个时要做另外的处理

算法伪代码如下：

if array.size = 1
then max = min = array[0]

max = Max(arr[0], arr[1]), min = Min(arr[0], arr[1])

for i <- 0 to size j <- i+1 to size
if max < Max(arr[i], arr[j])
then max = maxone

if min > Min(arr[i], arr[j])
then min = minone

if size is not even
then compare max and min with last element
got max and min

C++实现：

//solution 1
template <class T>
void FindMaxMin(T *arr, int size)
{
    T max = 0, min = 0;

    //if array.size = 1
    if(size == 1)
    {
        //max = min = array[0]
        cout << "max : " << arr[0] << " min : " << arr[0] << endl;
        return;
    }

    //max = Max(arr[0], arr[1]), min = Min(arr[0], arr[1])
    max = Max(arr[0], arr[1]);
    min = Min(arr[0], arr[1]);

    //for i <- 0 to size j <- i+1 to size
    for(int i = 0, j = i+1; i != size && j != size; ++i, ++j)
    {
        //if max < Max(arr[i], arr[j])
        if(max < Max(arr[i], arr[j]))
        {
            //then max = maxone
            max = Max(arr[i], arr[j]);
        }

        //if min > Min(arr[i], arr[j])
        if(min > Min(arr[i], arr[j]))
        {
            //then min = minone
            min = Min(arr[i], arr[j]);
        }
    }

    //if size is not even
    if(size%2 != 0)
    {
        //then compare max and min with last element
        if(max < arr[size-1])
        {
            max = arr[size-1];
        }
        if(min > arr[size-1])
        {
            min = arr[size-1];
        }
    }
    
    //got max and min
    cout << "max : " << max << " min : " << min << endl;
}

算法思路二：
采用分治的方法，先计算得到前后N/2个数的最大和最小值，再将N/2个数划分为两个数组分别求两个数组的最大值和最小值，以此类推，最后可以得到整个数组的最大值和最小值。

算法伪代码如下：

if remain 2 element or one element
then max = maxone, min = minone
FindMaxMin in 2 size/2 counts"array recursionly
max = maxone, min = minone

C++实现：

template <class T>
NumberPair<T> FindMaxMin(T * arr, int begin, int end)
{
    //if remain 2 element or one element
    if(end - begin <= 1)
    {
        //then max = maxone, min = minone
        NumberPair<T> n;
        if(arr[begin] < arr[end])
        {
            n.max = arr[end];
            n.min = arr[begin];
            return n;
        }
        else
        {
           n.max = arr[begin];
           n.min = arr[end];
           return n;
        }

    }
    //FindMaxMin in 2 size/2 counts"array recursionly
    NumberPair<T> L = FindMaxMin(arr, begin, begin + (end-begin) / 2);
    NumberPair<T> R = FindMaxMin(arr, begin + (end-begin) / 2 + 1, end);

    //max = maxone, min = minone
    NumberPair<T> result;
    result.max = Max(L.max, R.max);
    result.min = Min(L.min, R.min);

    return result;
}