【Python】求矩阵鞍点的几种思路-Toy模板网

这篇具有很好参考价值的文章主要介绍了【Python】求矩阵鞍点的几种思路。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

代码思路仅供参考，欢迎大家批评指正！

求矩阵鞍点的个数

一个矩阵元素的“鞍点”是指该位置上的元素值在该行上最大、在该列上最小。

本题要求编写程序，求一个给定的n阶方阵的鞍点。

题目详情

python中怎样利用bf算法求解马鞍点,Python,python,矩阵,算法

思路1

遍历矩阵m，判断每一个点是否为鞍点。时间复杂度为O(n³)

代码

# By jurio.
n = int(input())
m = []
for r in range(n):
    m.append(input().split())

c = 0
for i in range(n):
    for j in range(n):
        if m[i][j] == max([m[i][k] for k in range(n)]) and m[i][j] == min([m[k][j] for k in range(n)]):
            c+=1
print(c)

思路2

根据鞍点的特征——某一行最大值，即一行最多存在一个鞍点，所以只需遍历每一行判断当前行是否有鞍点即可。时间复杂度为O(n²)

代码

# By jurio.
n = int(input())
m = []
for r in range(n):
    m.append(input().split())

r0 = 0
saddle_point = 0
for r0 in range(n):
    max_id = [index for (index,value) in enumerate(m[r0]) if value == max(m[r0])]
    for id_i in max_id:
        if m[r0][id_i] == min(m[r][id_i] for r in range(n)):
            saddle_point += 1
print(saddle_point)