2.10 用最少次數尋找數組中的最大值和最小值[find min max of array]，2.10array

2.10 用最少次數尋找數組中的最大值和最小值[find min max of array]，2.10array

【本文鏈接】

http://www.cnblogs.com/hellogiser/p/find-min-max-of-array.html

【題目】

對於一個由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[i] a[j]
        getMinMax(a[i], 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;
}

【參考】

http://blog.csdn.net/caryaliu/article/details/8135898

http://www.cnblogs.com/lovell-liu/archive/2011/09/07/2169644.html

【本文鏈接】

http://www.cnblogs.com/hellogiser/p/find-min-max-of-array.html

用匯編語言將一未排序數組ARRAY中的最大值送入MAX中,最小值送入MIN中

.data
ARRAY dd 10 dup(?)
COUNT dd ?
MAX dd 0
MIN dd 0

.code

lea eax,ARRAY
mov ebx,[eax]
mov ecx,ebx
mov ecx,COUNT
dec ecx
add eax,4
s: cmp [eax],ebx
jg _Max
cmp [eax],edx
jl _Min
jmp _loop

_Max: mov ebx,[eax]
jmp _loop
_Min: mov edx,[eax]
_loop: add eax,4
loop s

mov MAX,ebx
mov MIN,edx
 

自己定義一個二維數組，找出數組中的最大值與最小值，並輸出結果

首先定義一個數組並初始化數據。
由於語言不同，需要先定義兩個變量rank1Count, rank2Count ;
int array [rank2Count ][rank1Count] ;
如果是Java/C#等還需要分配空間，如：int [][] array = new int [rank1Count][rank2Count] ;
然後初始化數據，當然也可以在定義的同時初始化。用{{1,2,3,4}, {4,5,6,7}}

然後遍歷整個數組，都是差不多的，
for (int i = 0 ; i < rank1Count; i ++)
{
for (int j = 0; j < rank2Count ; j ++)
{
int num = array [i][j] ;
}
}

檢查最大值最小值，首先定義兩個變量：int max = array [0][0] ; int min = array [0][0] ;
然後再循環中比較：
int num = array [i][j] ;
if (num > max) max = num ;
if (num < min) min = num ;

當然C也可以用宏 min () 和max () ;Java等可以用Math.min () Math.max () ;

int num = array [i][j] ;
max = max (max, num) ;
min = min (min, num) ;

輸出的話，不同的語言不一樣了，比如C:
printf ("Max = %d, min = %d\n" , max, min) ;
Java 的：
System.out.println ("Max = " + max + ", min = " + min) ;