algorithm - 具有排序行的矩阵的中值

Question

我无法以最佳方式解决以下问题，也无法在任何地方找到解决此问题的方法。

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

For example,

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

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

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

我们将不胜感激。

Answer 1

考虑以下过程。

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

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

  <

• 由于每行中的矩阵元素已排序，因此您可以轻松找到每行中小于或等于 x 的元素数。对于在整个矩阵中查找，复杂度为 N*log M，使用二分查找。

• 然后先从N*M矩阵中找出最小和最大元素。对该范围应用二分搜索并对每个 x 运行上述函数。

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

你可以考虑下面的 C++ 代码:

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;
}