在 C++ 中查找所有行中最小的公共元素

假设我们有一个矩阵 mat，其中每一行都是按非递减顺序排序的，我们需要找到所有行中最小的公共元素。如果没有公共元素，则返回 -1。所以如果矩阵如下所示：

12345
245810
357911
13579

输出将为 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 的键

  • 返回 -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

更新于: 2020年4月29日

158 次查看

开启你的 职业生涯

通过完成课程获得认证

立即开始
广告