Computer >> 컴퓨터 >  >> 프로그램 작성 >> C++

C++의 모든 행에서 가장 작은 공통 요소 찾기


모든 행이 내림차순으로 정렬된 행렬 매트가 있다고 가정하면 모든 행에서 가장 작은 공통 요소를 찾아야 합니다. 공통 요소가 없으면 -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

  • 0 ~ n – 1 범위의 i에 대해

    • 0 ~ x – 1 범위의 j에 대해

      • 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