C++で行列のすべての行に共通する最小要素を見つける方法

問題概要

各行が非降順(昇順)にソートされた行列 mat が与えられます。このとき、すべての行に共通して現れる最小の要素を求めてください。共通する要素が存在しない場合は -1 を返します。

例として、次のような行列を考えてみましょう。

この行列の場合、出力は 5 になります。すべての行に共通して登場する要素は 5 のみだからです。

解法のアプローチ

この問題は連想配列(std::map やハッシュマップ)を使うことで効率的に解けます。基本的な考え方は、「各行を順番に走査しながら、最初の行から現在の行まで連続して出現している要素だけをカウントアップする」というものです。手順は以下の通りです。

• マップ 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 増やします。
• マップ内の各キーと値のペアを調べます。
  • 値が n と一致するキー(= すべての行に出現した要素)が見つかったら、そのキーを返します。
• 該当するものが存在しなければ -1 を返します。

ここで重要になるのが条件式 m[mat[i][j]] + 1 == i + 1 です。これは「この要素が 0 行目から現在の行まで毎回出現しているか」を判定しており、重複する値が同じ行内にあっても正しく処理できます。また、std::map はキー順に自動ソートされるため、最後にマップを先頭から走査するだけで最小の共通要素を取得できる点もポイントです。

C++での実装例

それでは、上記のアルゴリズムを実際の 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

計算量の目安

時間計算量は O(n × x)(n は行数、x は列数)です。空間計算量は行列中に現れる異なる要素の数に依存します。なお、std::map は各操作に O(log) のコストがかかるため、unordered_map を使えばさらに高速化できます。ただし、その場合は最小のキーを自分で探索する処理を追加する必要がある点に注意しましょう。