i376 - 尋寶 (Treasure)
題目描述
題目給定一個 n x n 的矩陣，要求找到一個元素，該元素在其所在的列中是最小值，同時在其所在的行中是最大值。如果找不到這樣的元素，則輸出 "NO"。
解題思路
解題思路是分別計算每一行的最大值和每一列的最小值。然後，遍歷整個矩陣，檢查每個元素是否同時是其所在行的最大值和其所在列的最小值。如果找到這樣的元素，則輸出其行索引和列索引。如果遍歷完整個矩陣都沒有找到，則輸出 "NO"。
複雜度分析
- 時間複雜度: O(n^2)
- 空間複雜度: O(n)
程式碼
#include <iostream>
using namespace std;
int n,a[105][105],mai[105],mij[105],x=-1,y=-1;
int main(){
cin.tie(0); ios::sync_with_stdio(0);
cin >> n;
for(int i=0;i<n;++i)
for(int j=0;j<n;++j){
cin >> a[i][j];
mai[i]=max(mai[i],a[i][j]);
mij[j]=(i==0?a[i][j]:min(mij[j],a[i][j]));
}
for(int i=0;i<n&&x==-1;++i)
for(int j=0;j<n&&y==-1;++j)
if(a[i][j]==mai[i]&&a[i][j]==mij[j]){
x=i;
y=j;
}
(x==-1&&y==-1)?cout << "NO":cout << x << " " << y;
}