Description
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 less than O(m * n) time complexity.
Example 1:
Input: grid = [[1,1,2],[2,3,3],[1,3,4]]
Output: 2
Explanation: The elements of the matrix in sorted order are 1,1,1,2,2,3,3,3,4. The median is 2.
Example 2:
Input: grid = [[1,1,3,3,4]]
Output: 3
Explanation: The elements of the matrix in sorted order are 1,1,3,3,4. The median is 3.
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 500m and n are both odd.1 <= grid[i][j] <= 106grid[i] is sorted in non-decreasing order.
Solutions
Solution 1: Two Binary Searches
The median is actually the target = \left \lceil m × n⁄2 \right \rceil-th number after sorting.
We perform a binary search on the elements of the matrix x, counting the number of elements in the grid that are greater than x, denoted as cnt. If cnt \ge target, it means the median is on the left side of x (including x); otherwise, it is on the right side.
The time complexity is O(m × log n × log M), where m and n are the number of rows and columns of the grid, respectively, and M is the maximum element in the grid. The space complexity is O(1).
PythonJavaC++Go
class Solution:
def matrixMedian(self, grid: List[List[int]]) -> int:
def count(x):
return sum(bisect_right(row, x) for row in grid)
m, n = len(grid), len(grid[0])
target = (m * n + 1) >> 1
return bisect_left(range(10**6 + 1), target, key=count)(code-box)
class Solution {
private int[][] grid;
public int matrixMedian(int[][] grid) {
this.grid = grid;
int m = grid.length, n = grid[0].length;
int target = (m * n + 1) >> 1;
int left = 0, right = 1000010;
while (left < right) {
int mid = (left + right) >> 1;
if (count(mid) >= target) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
private int count(int x) {
int cnt = 0;
for (var row : grid) {
int left = 0, right = row.length;
while (left < right) {
int mid = (left + right) >> 1;
if (row[mid] > x) {
right = mid;
} else {
left = mid + 1;
}
}
cnt += left;
}
return cnt;
}
}(code-box)
class Solution {
public:
int matrixMedian(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
int left = 0, right = 1e6 + 1;
int target = (m * n + 1) >> 1;
auto count = [&](int x) {
int cnt = 0;
for (auto& row : grid) {
cnt += (upper_bound(row.begin(), row.end(), x) - row.begin());
}
return cnt;
};
while (left < right) {
int mid = (left + right) >> 1;
if (count(mid) >= target) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
};(code-box)
func matrixMedian(grid [][]int) int {
m, n := len(grid), len(grid[0])
count := func(x int) int {
cnt := 0
for _, row := range grid {
left, right := 0, n
for left < right {
mid := (left + right) >> 1
if row[mid] > x {
right = mid
} else {
left = mid + 1
}
}
cnt += left
}
return cnt
}
left, right := 0, 1000010
target := (m*n + 1) >> 1
for left < right {
mid := (left + right) >> 1
if count(mid) >= target {
right = mid
} else {
left = mid + 1
}
}
return left
}(code-box)
