具有排序行的矩阵的中位数 [英] Median of a Matrix with sorted rows

问题描述

我无法最佳地解决以下问题，也无法找到在任何地方进行此操作的方法.

I am not able to solve the following problem optimally nor finding an approach to do this anywhere.

给定一个N×M矩阵，其中每一行都被排序，找到矩阵的整体中位数.假设N * M为奇数.

Given a N × M matrix in which each row is sorted, find the overall median of the matrix. Assume N*M is odd.

例如

矩阵=
[1、3、5]
[2，6，9]
[3，6，9]

Matrix =
[1, 3, 5]
[2, 6, 9]
[3, 6, 9]

A = [1、2、3、3、5、6、6、9、9]

A = [1, 2, 3, 3, 5, 6, 6, 9, 9]

中位数为5.因此，我们返回5.
注意:不允许额外的内存.

Median is 5. So, we return 5.
Note: No extra memory is allowed.

任何帮助将不胜感激.

推荐答案

请考虑以下过程.

• 如果我们将N * M矩阵视为一维数组，则中位数是1+N*M/2个元素.

然后，如果x是矩阵的元素并且≤x的矩阵元素的数量等于1 + N*M/2，则认为x是中位数.

Then consider x will be the median if x is an element of the matrix and number of matrix elements ≤ x equals 1 + N*M/2.

在对每行中的矩阵元素进行排序时，您可以轻松地找到每行中的元素数less than or equals x.要在整个矩阵中查找，使用二进制搜索的复杂度为N*log M.

As the matrix elements in each row are sorted then you can easily find the number of elements in each row less than or equals x. For finding in the whole matrix, the complexity is N*log M with binary search.

然后首先从N * M矩阵中找到最小和最大元素.在该范围内应用二进制搜索，然后为每个x运行上述功能.

Then first find the minimum and maximum element from the N*M matrix. Apply Binary Search on that range and run the above function for each x.

如果矩阵≤ x中的元素数为1 + N*M/2并且x包含在该矩阵中，则x是中位数.

If the number of elements in matrix ≤ x is 1 + N*M/2 and x contains in that matrix then x is the median.

您可以在C ++代码下考虑此问题:

You can consider this below C++ Code :

int median(vector<vector<int> > &A) {
    int min = A[0][0], max = A[0][0];
    int n = A.size(), m = A[0].size();
    for (int i = 0; i < n; ++i) {
        if (A[i][0] < min) min = A[i][0];
        if (A[i][m-1] > max) max = A[i][m-1];
    }

    int element = (n * m + 1) / 2;
    while (min < max) {
        int mid = min + (max - min) / 2;
        int cnt = 0;
        for (int i = 0; i < n; ++i)
            cnt += upper_bound(&A[i][0], &A[i][m], mid) - &A[i][0];
        if (cnt < element)
            min = mid + 1;
        else
            max = mid;
    }
    return min;
}

这篇关于具有排序行的矩阵的中位数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！