C語言尋找二維陣列鞍點：完整演算法與代碼實作

什麼是鞍點？

在 m×n 矩陣中，若元素 a[i][j] 滿足：

• **該行最大值** ：a[i][j] ≥ a[i][k] 對所有 k
• **該列最小值** ：a[i][j] ≤ a[k][j] 對所有 k

則稱該位置為鞍點。矩陣可能有 0 個、1 個或多個鞍點。

演算法策略：預計算行極值與列極值

1. 掃描每行，記錄 **行最大值** 到 row_max[i]
2. 掃描每列，記錄 **列最小值** 到 col_min[j]
3. 遍歷所有位置，若 a[i][j] == row_max[i] && a[i][j] == col_min[j] 則為鞍點

時間複雜度：O(m×n)，空間複雜度：O(m+n)

完整 C 代碼（修正版）

#include <stdio.h>
#include <stdlib.h>

int main() {
    int rows, cols;
    printf("輸入行數: ");
    scanf("%d", &rows);
    printf("輸入列數: ");
    scanf("%d", &cols);

    // 動態分配二維陣列
    int **matrix = (int**)malloc(rows * sizeof(int*));
    for(int i = 0; i < rows; i++)
        matrix[i] = (int*)malloc(cols * sizeof(int));

    printf("請輸入 %d 個元素 (行優先):\n", rows * cols);
    for(int i = 0; i < rows; i++)
        for(int j = 0; j < cols; j++)
            scanf("%d", &matrix[i][j]);

    // 1. 計算每行最大值
    int *row_max = (int*)malloc(rows * sizeof(int));
    for(int i = 0; i < rows; i++) {
        row_max[i] = matrix[i][0];
        for(int j = 1; j < cols; j++)
            if(matrix[i][j] > row_max[i])
                row_max[i] = matrix[i][j];
    }

    // 2. 計算每列最小值
    int *col_min = (int*)malloc(cols * sizeof(int));
    for(int j = 0; j < cols; j++) {
        col_min[j] = matrix[0][j];
        for(int i = 1; i < rows; i++)
            if(matrix[i][j] < col_min[j])
                col_min[j] = matrix[i][j];
    }

    // 3. 尋找鞍點
    int found = 0;
    for(int i = 0; i < rows; i++) {
        for(int j = 0; j < cols; j++) {
            if(matrix[i][j] == row_max[i] && matrix[i][j] == col_min[j]) {
                printf("鞍點位於 matrix[%d][%d] = %d\n", i, j, matrix[i][j]);
                found = 1;
            }
        }
    }

    if(!found) printf("沒有鞍點\n");

    // 4. 釋放記憶體
    for(int i = 0; i < rows; i++) free(matrix[i]);
    free(matrix);
    free(row_max);
    free(col_min);

    return 0;
}

關鍵修正點（對比原代碼）

測試案例

輸入:
3 3
1 2 3
4 5 6
7 8 9

行最大: [3, 6, 9]
列最小: [1, 2, 3]
鞍點: matrix[0][2] = 3  (第0行最大、第2列最小)

輸入:
2 2
5 5
5 5

所有元素皆為鞍點 (同時滿足行最大、列最小)

進階變體

• 嚴格鞍點：行嚴格最大、列嚴格最小（需計算次大/次小值）
• 多維鞍點：張量中的廣義鞍點概念
• 博弈論應用：零和遊戲中的 Nash 平衡即為鞍點

總結

鞍點問題展示了「預計算極值 + 線性掃描」的經典技巧，將 O(m×n×(m+n)) 降為 O(m×n)。動態二維陣列分配、邊界條件處理、記憶體釋放規範是C語言工程實踐的關鍵點。