0378. Kth Smallest Element in a Sorted Matrix ============================================= 题目信息 -------- :题号: 0378 :难度: Medium :主题: 有序方阵、顺序统计量、重复值、排名 :原题: `LeetCode 0378 `_ :重点: 每行每列均非递减、第 k 小按全部元素位置计数、重复值分别占据排名、k 从 1 开始 题目重述 -------- 给定一个 ``n x n`` 整数方阵 ``matrix``,其中每一行从左到右、每一列从上到下都按非递减顺序排列。把矩阵中的 ``n^2`` 个元素整体按值排序,返回其中第 ``k`` 小的元素。 ``k`` 使用一基排名,位于 ``[1, n^2]``。矩阵边长位于 ``[1, 300]``,元素位于 ``[-10^9, 10^9]``。重复值不会去重,每次出现都占据一个独立排序位置;题目要求返回值,而不是矩阵坐标。 自建示例 -------- 重复值分别参与排名: .. code-block:: text 输入:matrix = [[1,2],[2,3]],k = 3 输出:2 解释:全部元素排序后为 [1,2,2,3],第三个元素仍然是 2。 单元素方阵: .. code-block:: text 输入:matrix = [[-5]],k = 1 输出:-5 解释:矩阵只有一个元素,它同时是第一小元素。 二分答案值,计数不超过它的元素 ------------------------------ 矩阵中的最小值和最大值给出了答案范围。对候选值 ``mid``,逐行用 ``upper_bound`` 统计小于等于 ``mid`` 的元素个数;这个计数随着 ``mid`` 增大单调不减。如果计数至少为 ``k``,第 ``k`` 小值不大于 ``mid``,收缩右边界;否则答案必须更大,移动左边界。 计数按出现次数累加,所以重复值不会被去重;最终二分找到的是第一个使计数达到 ``k`` 的值,也就是一基排名下的第 ``k`` 小元素。 C++ 实现 -------- .. code-block:: cpp class Solution { public: int kthSmallest(std::vector>& matrix, int k) { long long left = matrix[0][0]; long long right = matrix.back().back(); while (left < right) { long long middle = left + (right - left) / 2; int count = 0; for (const auto& row : matrix) { count += static_cast( std::upper_bound(row.begin(), row.end(), middle) - row.begin()); } if (count >= k) { right = middle; } else { left = middle + 1; } } return static_cast(left); } }; 代码分析 -------- ``upper_bound`` 利用每行有序性完成计数,二分利用“计数至少为 k”的单调性;行列同时有序但这里不需要额外构造元素堆。设边长为 ``n``、数值范围宽度为 ``V``,时间复杂度为 ``O(n log n log V)``,额外空间为 ``O(1)``。