2387. Median of a Row Wise Sorted Matrix
Given an m x n matrix grid containing an odd number of integers where each row is sorted in non-decreasing order, return the median of the matrix.
You must solve the problem in O(m * log(n)) time complexity.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
int matrixMedian(vector<vector<int>>& A) {
long long l = 0, r = INT_MAX, res = 0;
long long med = A.size() * A[0].size() / 2 + 1;
while(l <= r) {
long long m = l + (r - l) / 2;
long long now = 0;
for(int i = 0; i < A.size(); i++) {
now += end(A[i]) - lower_bound(begin(A[i]), end(A[i]), m);
}
if(now >= med) {
res = max(res, m);
l = m + 1;
} else r = m - 1;
}
return res;
}
};
|
