在C ++中按行排序的矩阵中找到中位数

Z时代
2024-01-10
分类：综合

在这个问题中，我们得到了一个二维数组mat [r] [c]，其元素按行排序。我们的任务是在按行排序的矩阵中查找中位数。

描述-我们需要找到矩阵元素的中位数。

让我们举个例子来了解这个问题，

输入

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

输出结果

解释

数组中存储的矩阵元素为＆minus

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

解决方法

解决此问题的简单方法是存储数组的所有元素。然后通过对数组进行排序来找到中值元素。

解决该问题的更有效方法是使用is在矩阵中恰好具有（r * c）/ 2个较小元素的事实来找到中值元素。我们将在符合此条件的数组中找到该元素。为此，我们将对矩阵进行二分查找，以矩阵的最小和最大元素为准，然后找到范围的中部并检查其中较小元素的数量。如果等于r * c / 2，则返回数字。如果它大于（r * c）/ 2，则将最大元素更改为小于找到的中间元素，如果计数小于（r * c）/ 2，则对最小元素进行相同操作。

小于中间元素的元素计数，我们可以通过查找大于中间元素的第一个元素的索引来按行对所有元素进行计数，也可以仅使用upper_bound（这是c ++中的内置函数）。

该程序说明了我们解决方案的工作原理，

示例

#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<<"矩阵的中位数是 "<<findMedian(mat);
   return 0;
}