Rust 练习册 98：探索矩阵中的鞍点

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

在数学与计算机科学领域，矩阵作为一种关键的数据结构，被广泛运用于图形处理、机器学习、游戏开发等多个方向。本文将深入探讨一个有趣的矩阵问题——鞍点（Saddle Points）的识别。

理解鞍点的概念

从数学角度来看，矩阵中的某个元素若在其所在的行中为最大值，同时在其所在的列中为最小值，则该元素被称为鞍点。这一名称源于其几何形态类似于马鞍：在一个维度上达到峰值，在另一个维度上则处于谷底。

考虑如下矩阵示例：

[1 2 3]
[4 5 6]
[7 8 9]

在此矩阵中，元素5既不是所在行的最大值，也不是所在列的最小值，因此不构成鞍点。

现在我们将矩阵调整为以下形式：

[1 2 3]
[4 1 6]
[7 8 9]

此时，元素1在其所在行中是最小值，而在其所在列中却是最大值，满足鞍点定义，故其为一个鞍点。

问题描述

我们的目标是实现一个函数，用于检测给定二维矩阵中所有鞍点的位置。函数签名如下：

pub fn find_saddle_points(input: &[Vec<u64>]) -> Vec<(usize, usize)>

该函数接收一个二维向量作为输入，返回一个包含所有鞍点坐标（行索引，列索引）的向量。

解决思路与实现

为了高效找出所有鞍点，可以采用以下策略：

• 遍历每个元素，判断其是否为其所在行的最大值；
• 同时判断其是否为其所在列的最小值；
• 只有当两个条件同时满足时，该位置才被视为鞍点。

为提升效率，可预先计算每行的最大值和每列的最小值，避免重复扫描。具体实现如下：

pub fn find_saddle_points(input: &[Vec<u64>]) -> Vec<(usize, usize)> {
    if input.is_empty() || input[0].is_empty() {
        return vec![];
    }
    let rows = input.len();
    let cols = input[0].len();

    let mut row_max = vec![0; rows];
    let mut col_min = vec![u64::MAX; cols];

    for i in 0..rows {
        for j in 0..cols {
            row_max[i] = row_max[i].max(input[i][j]);
            col_min[j] = col_min[j].min(input[i][j]);
        }
    }

    let mut saddle_points = Vec::new();
    for i in 0..rows {
        for j in 0..cols {
            let value = input[i][j];
            if value == row_max[i] && value == col_min[j] {
                saddle_points.push((i, j));
            }
        }
    }
    saddle_points
}

测试用例解析

通过分析多个测试案例，有助于全面理解算法对边界情况的处理能力。

单个鞍点情况：

#[test]
fn identify_single_saddle_point() {
    let input = vec![vec![9, 8, 7], vec![5, 3, 2], vec![6, 6, 7]];
    assert_eq!(vec![(1, 0)], find_saddle_points(&input));
}

其中，位置 (1, 0) 的元素 5 是第1行的最大值，同时也是第0列的最小值，因此为唯一鞍点。

空矩阵处理：

#[test]
fn identify_empty_matrix() {
    let input = vec![vec![], vec![], vec![]];
    let expected: Vec<(usize, usize)> = Vec::new();
    assert_eq!(expected, find_saddle_points(&input));
}

对于空矩阵，显然不存在任何有效元素，因此返回空结果。

一列中存在多个鞍点：

#[test]
fn multiple_saddle_points_in_col() {
    let input = vec![vec![4, 5, 4], vec![3, 5, 5], vec![1, 5, 4]];
    assert_eq!(
        vec![(0, 1), (1, 1), (2, 1)],
        find_sorted_saddle_points(&input)
    );
}

本例中，第1列的所有元素均为5，且为该列的最小值；同时它们也是各自所在行的最大值，因此整列都为鞍点。

识别全部鞍点：

最后一个测试旨在验证系统能否正确识别复杂矩阵中所有符合条件的鞍点，确保算法鲁棒性和完整性。

let input = vec![vec![5, 5, 5], vec![5, 5, 5], vec![5, 5, 5]];
assert_eq!(
    vec![
        (0, 0),
        (0, 1),
        (0, 2),
        (1, 0),
        (1, 1),
        (1, 2),
        (2, 0),
        (2, 1),
        (2, 2)
    ],
    find_sorted_saddle_points(&input)
);

当矩阵中的所有元素值都相同，每一个元素同时满足是其所在行的最大值与所在列的最小值，因此整个矩阵的所有位置均为鞍点。

算法优化说明

当前实现采用预处理策略：首先遍历矩阵，分别记录每一行的最大值和每一列的最小值。随后再次遍历矩阵，检查每个位置是否等于其行最大值且等于其列最小值。该方法将时间复杂度控制在 O(rows × cols)，相比对每个元素重复计算对应行列极值的方式，显著提升了效率。

实际应用场景

鞍点问题不仅具有数学理论意义，在多个领域中也有广泛用途：

• 博弈论：在零和博弈中，鞍点对应双方的最优策略组合，表示纳什均衡的一种特殊情况。
• 优化理论：多变量函数的鞍点是一种临界点，既非局部极大也非局部极小，对理解函数地形至关重要。
• 图像处理：利用鞍点进行特征提取和边缘检测，有助于识别图像中的关键结构。
• 经济学：在供需模型中，可通过寻找平衡点来分析市场稳定状态，类似鞍点的性质可用于定位均衡解。

总结与收获

通过本题的实践，我们深入掌握了以下几个核心编程技能：

1. 二维矩阵的数据访问与索引处理；
2. 按行和按列进行统计量（如最值）的提取；
3. 通过预计算优化算法性能，避免重复运算；
4. 正确处理边界情况，例如全等元素矩阵等特殊输入。

这些问题在日常开发和算法设计中频繁出现，熟练掌握其解决思路对于提升编程能力大有裨益。同时，Rust语言凭借其内存安全机制与接近C/C++的运行效率，成为处理数值密集型任务的理想工具之一。

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：练习册 identify Expected Multiple saddle

相关内容：Rust练习册探索