C++에서 주어진 행별로 정렬된 행렬의 모든 행에서 공통 요소 찾기

각 행이 정렬된 행렬이 있다고 가정합니다. 각 행에서 공통 요소를 찾는 함수를 작성해야 합니다. 행렬이 아래와 같다고 가정 -

결과는 5입니다.

이를 해결하기 위해 해시 기반 접근 방식을 사용합니다. 이 접근 방식은 행이 정렬되지 않은 경우에도 사용할 수 있습니다. 이렇게 하려면 몇 가지 단계를 따라야 합니다 -

2개의 1의 고유한 요소로 모든 키를 사용하여 하나의 해시 테이블을 생성합니다. 모든 값은 0이 됩니다.

행렬의 각 요소를 순환하면서 해시 테이블에 숫자가 있으면 개수를 1만큼 늘립니다. 마지막으로 개수가 행렬의 행 번호와 같은 값이 있는지 확인합니다. 그렇다면 각 행에 존재합니다. (한 값이 한 행에서 반복되지 않는다고 가정)

예시

#include<iostream>
#include<unordered_map>
#define M 4
#define N 5
using namespace std;
int getCommonElement(int matrix[M][N]) {
   unordered_map<int, int> count;
   int i, j;
   for (i = 0; i < M; i++) {
      count[matrix[i][0]]++;
      for (j = 1; j < N; j++) {
         if (matrix[i][j] != matrix[i][j - 1])
         count[matrix[i][j]]++;
      }
   }
   for (auto ele : count) {
      if (ele.second == M)
      return ele.first;
   }
   return -1;
}
int main() {
   int matrix[M][N] = {
      { 1, 2, 3, 4, 5 },
      { 2, 4, 5, 8, 10 },
      { 3, 5, 7, 9, 11 },
      { 1, 3, 5, 7, 9 },
   };
   int result = getCommonElement(matrix);
   if (result == -1)
      cout << "No common element has found";
   else
      cout << "Common element is " << result;
}

출력

Common element is 5