C++でソート済み行列内のx以下の要素数を数える方法

概要

n × n のサイズの行列と整数 x が与えられます。行列の各要素はソート済みの状態で配置されており、課題は「x 以下の値を持つ要素がいくつあるか」を求めることです。

それでは、具体的な入出力例を見ていきましょう。

入力例1

matrix[3][3] = {{1, 2, 3}, {4, 5, 6}, {6, 7, 8}}、X = 4

出力例1

count is 4

説明： 行列の各要素と x（= 4）を比較すると、x 以下となる要素は 1, 2, 3, 4 の 4 つです。したがって、カウントは 4 となります。

入力例2

matrix[3][3] = {{1, 2, 3}, {4, 5, 6}, {6, 7, 8}}、X = 0

出力例2

count is 0

説明： 行列の中に x（= 0）以下の値を持つ要素は存在しないため、カウントは 0 となります。

アルゴリズムのアプローチ

この問題は、以下の手順で解くことができます。

• 行列のサイズ n を入力として受け取り、n × n の行列を作成します。
• 外側のループ変数 i を 0 から行サイズまで回します。
• 内側のループ変数 j を 0 から列サイズまで回します。
• matrix[i][j] が x 以下であるかどうかを判定し、条件を満たしていればカウントを 1 増やします。満たさない場合は何もしません。
• ループ終了後、合計カウントを返します。
• 結果を出力します。

C++実装例

#include <bits/stdc++.h>
using namespace std;
#define size 3
// 要素数をカウントする関数
int count(int matrix[size][size], int x){
   int count=0;
   // 行ごとに行列を走査
   for(int i = 0 ;i<size; i++){
      for (int j = 0; j<size ; j++){
         // 行列の値がx以下であるかどうかをチェック
         if(matrix[i][j]<= x){
            count++;
         }
      }
   }
   return count;
}
int main(){
   int matrix[size][size] ={
      {1, 2, 3},
      {4, 5, 6},
      {7, 8, 9}
   };
   int x = 5;
   cout<<"Count of elements smaller than or equal to x in a sorted matrix is: "<<count(matrix,x);
   return 0;
}

実行結果

上記のコードを実行すると、以下の出力が得られます。

Count of elements smaller than or equal to x in a sorted matrix is: 5

計算量について

このアプローチでは、行列のすべての要素を一度ずつ走査するため、時間計算量は O(n²) となります。一方、空間計算量は O(1) で、追加のメモリは不要です。

なお、行列が行・列ともにソートされているという性質を活かせば、各行に対して二分探索（バイナリサーチ）を用いることで O(n log n) まで高速化することも可能です。さらに効率化したい場合は、階段探索（右上または左下から探索を始める方法）なども検討できます。