在 C++ 中查找所有行中的最小公共元素
c++server side programmingprogramming
假设我们有一个矩阵 mat，其中每行都按非递减顺序排序，我们必须找到所有行中的最小公共元素。如果没有公共元素，则返回 -1。因此，如果矩阵像 −
| 1 | 2 | 3 | 4 | 5 |
| 2 | 4 | 5 | 8 | 10 |
| 3 | 5 | 7 | 9 | 11 |
| 1 | 3 | 5 | 7 | 9 |
输出将为 5
为了解决这个问题，我们将遵循以下步骤 −
定义一个映射 m, n := 矩阵的行数，
如果 n 不为 0，则 x = 列大小，否则0
对于 i 在 0 到 n 范围内 – 1
对于 j 在 0 到 x 范围内 – 1
如果 m[mat[i, j]] + 1 = i + 1，则将 m[mat[i, j]] 增加 1
对于每个键值对 i
如果 i 的值为 n，则返回 i 的键
return -1
示例 (C++)
让我们看下面的实现，以便更好地理解 −
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int smallestCommonElement(vector<vector<int>>& mat) {
map <int, int> m;
int n = mat.size();
int x = n? mat[0].size() : 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < x; j++){
if(m[mat[i][j]] + 1 == i + 1){
m[mat[i][j]]++;
}
}
}
map <int, int> :: iterator it = m.begin();
while(it != m.end()){
if(it->second == n){
return it->first;
}
it++;
}
return -1;
}
};
main(){
vector<vector<int>> v = {{1,2,3,4,5},{2,4,5,8,10},{3,5,7,9,11},{1,3,5,7,9}};
Solution ob;
cout << (ob.smallestCommonElement(v));
}
输入
[[1,2,3,4,5],[2,4,5,8,10],[3,5,7,9,11],[1,3,5,7,9]]
输出
5
