代碼思路僅供參考，歡迎大家批評指正！
求矩陣鞍點的個數(shù)
一個矩陣元素的“鞍點”是指該位置上的元素值在該行上最大、在該列上最小。
本題要求編寫程序，求一個給定的n階方陣的鞍點。
題目詳情
思路1
遍歷矩陣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
根據(jù)鞍點的特征——某一行最大值，即一行最多存在一個鞍點，所以只需遍歷每一行判斷當前行是否有鞍點即可。時間復雜度為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
我們知道鞍點不僅是某一行最大值，同時是該行最大值那一列的最小值。那么理論上可以用下面的算法進行查找：
- 從第一行開始找到最大值，然后判斷是否為當前列最小值；
- 若是最小值則鞍點個數(shù)+1，同時該列可以排除（后續(xù)檢索到該列直接跳過），然后行數(shù)+1重新開始；
- 若不是則找到該列最小值，將最小值所在行作為新的起點，并判斷該最小值是否為鞍點；
- 若是鞍點則+1，排除當前行和列；
- 若不是則排除列，同時繼續(xù)尋找該行最大值，即回歸第1步。
上述思路可以使用兩個列表來存儲已排除的行和列，并在遍歷時判斷當前行列是否已在排除列表。理論上時間復雜度應該為O(nlogn)文章來源：http://www.zghlxwxcb.cn/news/detail-774506.html
PTA暫時無法使用numpy，用列表實現(xiàn)比較困難暫時沒有代碼實現(xiàn)，上述算法僅代表個人看法，思路不對的地方希望大家批評指正。文章來源地址http://www.zghlxwxcb.cn/news/detail-774506.html
到了這里，關于【Python】求矩陣鞍點的幾種思路的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
