数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学在C++中查找行排序矩阵的中位数
在这个问题中，我们得到一个二维数组mat[r][c]，其元素按行排序。我们的任务是在行排序矩阵中查找中位数。
描述 - 我们需要找到矩阵元素的中位数。
让我们举个例子来理解这个问题：
输入
mat = {
{2, 4, 7},
{5, 6, 8},
{4, 8, 9}
}输出
6
解释
存储在数组中的矩阵元素为：
{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
更新于：2021年3月12日
212 次浏览
广告