C++で特定の行ごとにソートされた行列のすべての行で共通の要素を検索します

各行がソートされている行列があるとします。各行の共通要素を見つける関数を作成する必要があります。マトリックスが次のようになっていると仮定します-

結果は5になります。

これを解決するために、ハッシュベースのアプローチを使用します。このアプローチは、行がソートされていない場合にも使用できます。これを行うには、いくつかの手順に従う必要があります-

2つの1の個別の要素としてすべてのキーを含む1つのハッシュテーブルを作成します。すべての値は0になります

行列の各要素をループします。ハッシュテーブルに数値が存在する場合は、カウントを1増やします。最後に、行列の行番号と同じカウントの値があるかどうかを確認します。もしそうなら、それは各行に存在します。 （1つの値が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