极客笔记C++程序 在按行排序的矩阵中找到中位数
在处理矩阵问题时，找到矩阵的中位数可能是一个常见的需求。本文将介绍如何用C++语言编写一个程序，在按行排序的矩阵中找到中位数。
问题描述
假设有一个n行m列的矩阵，矩阵按行排序，即每行的所有元素均不降序排列。请编写一个C++程序来找到矩阵的中位数。
例如，假设矩阵如下所示：
1 3 5
2 4 6
7 8 9
中位数为4。
解决方案
在考虑如何编写程序之前，我们需要了解什么是矩阵的中位数。如果矩阵中元素的个数是奇数，那么中位数就是排序后的第 n/2 + 1 个元素；如果矩阵中元素的个数是偶数，那么中位数就是排序后的第 n/2 和第n/2+1个元素的平均值。
因此，我们需要找到中位数在排序后在矩阵的哪个位置。
首先，我们可以将每行的元素插入到一个大小为n的数组中，然后对数组排序。接下来，我们可以使用快速选择算法（Quickselect）在数组中找到中位数。
快速选择算法是一种通用的算法，用于在未排序的数组中查找第k小的元素。它的平均时间复杂度为O(n)，最坏情况下的时间复杂度为O(n^2)。由于我们只需要找到一个数，所以理论上快速选择算法比快速排序算法更快。
接下来，让我们看一下如何将这些思想转换成C++代码。
代码实现
首先，我们需要自定义一个比较函数，用于对数组进行排序。
bool compare(int a, int b) {
return a < b;
}
接下来，我们可以定义一个函数findMedian，该函数接收一个二维数组，返回中位数。
double findMedian(vector<vector<int>>& matrix) {
int n = matrix.size(), m = matrix[0].size();
int k = (n * m + 1) / 2; // 找到中位数在排序后的位置
int left = INT_MIN, right = INT_MAX;
while (left < right) {
int mid = (left + right) / 2;
int count = 0;
// 统计小于mid的元素的个数
for (int i = 0; i < n; i++) {
count += upper_bound(matrix[i].begin(), matrix[i].end(), mid, compare) - matrix[i].begin();
}
// 如果小于mid的元素的个数小于k个，则中位数一定大于mid
if (count < k) {
left = mid + 1;
}
else {
right = mid;
}
}
return left;
}
函数内部使用了二分查找的思想来快速找到中位数所在的位置。在每一轮迭代中，我们首先计算比mid小的元素的数量，然后判断mid是否为中位数。如果小于k个，则说明中位数一定大于mid；如果大于等于k个，则说明中位数一定小于等于mid。
在上面的代码中，我们使用了STL中的upper_bound函数来统计小于mid的元素的数量。upper_bound函数搜索第一个大于给定值的位置。此时，该位置前面的元素均小于等于mid，因此我们可以通过该位置的下标来计算小于mid的元素的数量。
最后，我们只需要计算left即为中位数。
完整的代码实现如下：
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
bool compare(int a, int b) {
return a < b;
}
double findMedian(vector<vector<int>>& matrix) {
int n = matrix.size(), m = matrix[0].size();
int k = (n * m + 1) / 2;
int left = INT_MIN, right = INT_MAX;
while (left < right) {
int mid = (left + right) / 2;
int count = 0;
for (int i = 0; i < n; i++) {
count += upper_bound(matrix[i].begin(), matrix[i].end(), mid, compare) - matrix[i].begin();
}
if (count < k) {
left = mid + 1;
}
else {
right = mid;
}
}
return left;
}
int main() {
vector<vector<int>> matrix{{1, 3, 5}, {2, 4, 6}, {7, 8, 9}};
double res = findMedian(matrix);
cout << res << endl; // 4.0
return 0;
}
结论
在本文中，我们介绍了如何使用C++编写程序，在按行排序的矩阵中查找中位数。我们使用了快速选择算法，该算法可以在O(n)的时间复杂度内查找未排序的数组中的第k小的元素。在二维矩阵中查找中位数时，我们将每一行的元素插入到单独的数组中，并对数组排序，然后使用快速选择算法在这些数组中查找中位数。最终，我们找到了矩阵的中位数，该算法的时间复杂度为O(n*log(m))。