【Python】求矩阵鞍点的几种思路 |
您所在的位置：网站首页 › python几行几列 › 【Python】求矩阵鞍点的几种思路 |
【Python】求矩阵鞍点的几种思路
|
代码思路仅供参考，欢迎大家批评指正！ 目录 求矩阵鞍点的个数题目详情思路1代码 思路2代码 思路3 求矩阵鞍点的个数一个矩阵元素的“鞍点”是指该位置上的元素值在该行上最大、在该列上最小。 本题要求编写程序，求一个给定的n阶方阵的鞍点。 题目详情
遍历矩阵m，判断每一个点是否为鞍点。时间复杂度为O(n3) 代码 # 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(n2) 代码 # 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) 思路3我们知道鞍点不仅是某一行最大值，同时是该行最大值那一列的最小值。那么理论上可以用下面的算法进行查找： 从第一行开始找到最大值，然后判断是否为当前列最小值；若是最小值则鞍点个数+1，同时该列可以排除（后续检索到该列直接跳过），然后行数+1重新开始；若不是则找到该列最小值，将最小值所在行作为新的起点，并判断该最小值是否为鞍点；若是鞍点则+1，排除当前行和列；若不是则排除列，同时继续寻找该行最大值，即回归第1步。上述思路可以使用两个列表来存储已排除的行和列，并在遍历时判断当前行列是否已在排除列表。理论上时间复杂度应该为O(nlogn) PTA暂时无法使用numpy，用列表实现比较困难暂时没有代码实现，上述算法仅代表个人看法，思路不对的地方希望大家批评指正。 |
【本文地址】