java 解法, 执行用时: 78 ms, 内存消耗: 64.9 MB, 提交时间: 2023-10-16 22:03:13

class Solution {
    public int matrixMedian(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        Queue<int[]> q = new PriorityQueue<>(new Comparator<int[]>() {

            @Override
            public int compare(int[] o1, int[] o2) {
                return Integer.compare(grid[o1[0]][o1[1]], grid[o2[0]][o2[1]]);
            }

        });

        for (int i = 0; i < m; ++i) {
            q.offer(new int[] { i, 0 });
        }
        int cur = 0;
        while (!q.isEmpty()) {
            int[] p = q.poll();
            int x = p[0];
            int y = p[1];

            if (cur == m * n / 2) {
                return grid[x][y];
            }
            if (++y < n) {
                q.offer(new int[] { x, y });
            }
            ++cur;
        }
        return -1;

    }
}

cpp 解法, 执行用时: 112 ms, 内存消耗: 34.7 MB, 提交时间: 2023-10-16 22:02:39

class Solution {
public:
    bool check(int x, int target, vector<vector<int>>& grid) {
        int cnt = 0;
        for (auto &row : grid) {
            cnt += lower_bound(row.begin(), row.end(), x) - row.begin();
        }
        return cnt <= target;
    }

    int matrixMedian(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int target = m * n / 2;

        int left = 1e6, right = 1;
        for (auto &row : grid) {
            left = min(left, row.front());
            right = max(right, row.back());
        }
        
        int ans = left;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (check(mid, target, grid)) {
                left = mid + 1;
                ans = mid;
            } else {
                right = mid - 1;
            }
        }
        return ans;
    }
};

python3 解法, 执行用时: 84 ms, 内存消耗: 45.9 MB, 提交时间: 2023-10-16 22:02:26

class Solution:
    def matrixMedian(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])

        def check(x: int) -> bool:
            cnt = 0
            for row in grid:
                cnt += bisect_left(row, x)
            return cnt <= m * n // 2
        
        left = min(row[0] for row in grid)
        right = max(row[-1] for row in grid)
        ans = left
        while left <= right:
            mid = (left + right) // 2
            if check(mid):
                left = mid + 1
                ans = mid
            else:
                right = mid - 1
        return ans