C++で行ごとにソートされた行列の中央値を検索します

この問題では、要素が行ごとにソートされている2D配列mat[r][c]が与えられます。私たちのタスクは、行ごとに並べ替えられた行列の中央値を見つけることです。

説明 −行列の要素の中央値を見つける必要があります。

問題を理解するために例を見てみましょう

入力

mat = {
   {2, 4, 7},
   {5, 6, 8},
   {4, 8, 9}
}

出力

6

説明

配列に格納されている行列の要素は＆minus

{2, 4, 4, 5, 6, 7, 8, 8, 9}
The median is 6.

ソリューションアプローチ

この問題の簡単な解決策は、配列のすべての要素を格納することです。次に、配列を並べ替えて中央値要素を見つけます。

この問題のより効果的な解決策は、行列内に正確に（r * c）/2小さい要素があるという事実を使用して中央値要素を見つけることです。そして、この条件に従う配列内の要素を見つけます。このために、マトリックスの最小要素と最大要素を取得するマトリックスの二分探索を使用し、次に範囲の中央を見つけて、その中の小さい要素の数を確認します。 r * c / 2に等しい場合は、数値を返します。 （r * c）/ 2より大きい場合は、最大の要素を検出された中央よりも小さい要素に変更し、カウントが（r * c）/ 2より小さい場合は、最小の要素に対して同じことを行います。

真ん中の要素よりも小さい要素の数。真ん中よりも大きい最初の要素のインデックスを見つけることによってすべての要素を行ごとに数えるか、c++の組み込み関数であるupper_boundを使用することができます。

ソリューションの動作を説明するプログラム

例

#include<bits/stdc++.h>
using namespace std;
#define c 3
#define r 3
int findMedian(int mat[][c]) {
   int smallest = INT_MAX, largest = INT_MIN;
   for (int i=0; i<r; i++) {
      if (mat[i][0] < smallest)
         smallest = mat[i][0];
      if (mat[i][c-1] > largest)
         largest = mat[i][c-1];
   }
   while (smallest < largest){
      int mid = smallest + (largest - smallest) / 2;
      int smallCount = 0;
      for (int i = 0; i < r; ++i)
         smallCount += upper_bound(mat[i], mat[i]+c, mid) -
      mat[i];
      if (smallCount < ( (r * c + 1) / 2 ))
         smallest = mid + 1;
      else
         largest = mid;
   }
   return smallest;
}
int main(){
   int mat[][c]= { {2, 5, 7}, {4, 6, 8}, {1, 8, 9} };
   cout<<"The median of the matrix is "<<findMedian(mat);
   return 0;
}

出力

The median of the matrix is 6