找出一个人二维数组中的鞍点,即该位置上的元素在该行上最大,在该列上最小。也可能没有鞍点
时间: 2024-11-27 15:14:01 浏览: 38
在一个二维数组(矩阵)中寻找鞍点是指找到一个位置,其元素同时满足两个条件:在所在的行中是最小值,而在所在的列中却是最大值。形象地说,就像马鞍的形状一样,两边高,中间低。如果数组里不存在这样的元素,那么就称没有鞍点。
查找鞍点的过程通常通过两层循环完成。首先遍历每一行,记录每个位置的最大值;然后对于每一列,检查当前列的最大值是否等于之前记录的行的最大值,如果是,则找到了一个可能的鞍点。最后,需要验证这个候选点是否同时满足列中的最小值条件。
以下是简单的Python示例:
```python
def find_saddle_point(matrix):
if not matrix or not matrix[0]:
return None
row_max = [float('-inf')] * len(matrix)
col_min = float('inf')
for i, row in enumerate(matrix):
row_max[i] = max(row)
for j in range(len(matrix[0])):
if matrix[j][j] > row_max[j] and matrix[j][j] < col_min:
col_min = min(matrix[j])
for i, row in enumerate(matrix):
if row_max[i] == matrix[i][j] and matrix[i][j] == col_min:
return (i, j) if col_min != float('inf') else None
return None
# 示例
matrix = [[9, 8, 7], [6, 5, 3], [4, 1, 2]]
saddle_point = find_saddle_point(matrix)
if saddle_point:
print(f"鞍点坐标是 {saddle_point},值为 {matrix[saddle_point]}")
else:
print("没有找到鞍点")
```
阅读全文