求解馬鞍點問題

題目描述

若矩陣An*m中某個元素A[i][j]是矩陣第i行中值最小的元素，同時又是第j列中值最大的元素，則稱元素A[i][j]是矩陣中的一個馬鞍點。設以二維數組存儲矩陣，編寫算法求矩陣A中的所有馬鞍點，算法的時間複雜度要盡量的低。

注意當最大值（最小值）并列相等時，會出現多鞍點的情況。

輸入

第一行輸入矩陣的總行數M和總列數N，以空格間隔。

之後的M行，依次輸入矩陣的各行資料，以空格間隔。

輸出

若有馬鞍點，則以行序為主序，依次輸出各個馬鞍點。每個馬鞍點以（row,col,val）的形式輸出，其中row 代表馬鞍點的行号，col代表馬鞍點的列号，val代表馬鞍點的值。若無馬鞍點，則輸出“NONE”。

樣例輸入

4 6

45 67 87 34 56 26

93 75 85 75 92 75

94 85 96 75 78 75

23 17 75 28 98 61

樣例輸出

(2,4,75)(2,6,75)(3,4,75)(3,6,75)

代碼

#include<stdio.h>
#include<stdlib.h>
 
 
int main()
{
    int m = 0;
    int n = 0;
 
    int i = 0;
    int j = 0;
 
    int flag = 0;
    int num = 0;
 
    int* min = (int *)malloc(n * sizeof(int));
    int* max = (int *)malloc(m * sizeof(int));
 
    scanf("%d%d", &m, &n);
    int **arr = (int**)malloc(m * sizeof(int *));
    for (i = 0; i < m; i++)
    {
        arr[i] = (int *)malloc(n * sizeof(int));
        for (j = 0; j < n; j++)
        {
            scanf("%d", &arr[i][j]);
        }
    }
 
    for (i = 0; i < m; i++)
    {
        min[i] = arr[i][0];
        for (j = 1; j < n; j++)
        {
            if (arr[i][j] < min[i])
            {
                min[i] = arr[i][j];
            }
        }
    }
 
    for (j = 0; j < n; j++)
    {
        max[j] = arr[0][j];
        for (i = 1; i < m; i++)
        {
            if (arr[i][j] > max[j])
            {
                max[j] = arr[i][j];
            }
        }
    }
 
    for (i = 0; i < m; i++)
    {
        if (flag == 1 && min[i] != num)
            continue;
        for (j = 0; j < n; j++)
        {
            if (min[i] == arr[i][j] && max[j] == arr[i][j])
            {
                if (flag == 0)
                { 
                    flag = 1;
                    num = arr[i][j];
                }
                printf("(%d,%d,%d)", i + 1, j + 1, arr[i][j]);
            }
        }
    }
 
    if (flag == 0)
    {
        printf("NONE");
    }
    return 0;
}