找出一个矩阵中的鞍点(鞍点是指数组中满足:在其所在行为最大,在其所在列为最小的元素),若存在鞍点,输出其所在行的行、列及鞍点的值。若不存在鞍点,则输出“NO”。
时间: 2024-11-06 15:36:55 浏览: 16
要找到一个矩阵中的鞍点,你可以遍历矩阵的每个元素,同时跟踪当前的最大值(行最大)和最小值(列最小)。对于每个元素,如果你发现它的值大于等于最大值并且小于等于最小值,那么这个元素就是一个鞍点候选。你需要检查这个元素是否与其所在的行中的所有元素以及与所在列的所有元素相比都满足这些条件。
以下是一个简单的C++函数,用于查找并返回鞍点的位置和值:
```cpp
#include <vector>
// 假设 matrix 是一个二维整数向量
std::pair<int, std::pair<int, int>> findHillValley(const std::vector<std::vector<int>>& matrix) {
if (matrix.empty() || matrix[0].empty()) {
return {"NO", {}};
}
// 初始化最大值、最小值及其对应的行和列索引
int max_value = matrix[0][0];
int min_value = matrix[0][0];
int row_max = 0;
int col_min = 0;
for (int i = 0; i < matrix.size(); ++i) {
for (int j = 0; j < matrix[i].size(); ++j) {
// 更新最大值和最小值,如果必要的话
if (matrix[i][j] > max_value && matrix[i][j] <= matrix[row_max][j]) {
max_value = matrix[i][j];
row_max = i;
}
if (matrix[i][j] < min_value && matrix[i][j] >= matrix[i][col_min]) {
min_value = matrix[i][j];
col_min = j;
}
}
}
// 检查是否存在鞍点,即最大值等于最小值
if (max_value == min_value) {
return {"NO", {}};
} else {
return {row_max + 1, {col_min + 1, max_value}}; // 返回行号+1和列号+1,因为索引从0开始
}
}
```
在这个函数中,我们首先处理空矩阵的情况。然后,遍历矩阵,更新最大值、最小值及其对应位置。最后,如果最大值不等于最小值,我们就找到了一个鞍点,并返回其位置和值;否则,返回"NO"表示没有鞍点。
阅读全文