GESP 五级 · GESP 202509 C++ 五级 第 10 题

给定一个 $n \times n$ 的矩阵 matrix，矩阵的每一行和每一列都按升序排列。函数 countLE 返回矩阵中第 $k$ 小的元素，则两处横线上应分别填写（ ）。

// 统计矩阵中 <= x 的元素个数：从左下角开始
int countLE(const vector<vector<int>>& matrix, int x) {
    int n = (int)matrix.size();
    int i = n - 1, j = 0, cnt = 0;
    while (i >= 0 && j < n) {
        if (matrix[i][j] <= x) {
            cnt += i + 1;
            ++j;
        } else {
            --i;
        }
    }
    return cnt;
}

int kthSmallest(vector<vector<int>>& matrix, int k) {
    int n = (int)matrix.size();
    int lo = matrix[0][0];
    int hi = matrix[n - 1][n - 1];

    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (countLE(matrix, mid) >= k) {
            _________________ // 在此处填入代码
        } else {
            _________________ // 在此处填入代码
        }
    }
    return lo;
}

A.

hi = mid - 1;
lo = mid + 1;

B.

hi = mid;
lo = mid;

C.

hi = mid;
lo = mid + 1;

D.

hi = mid + 1;
lo = mid;

STL 容器：vector（动态数组）、set/map（红黑树，有序）、unordered_set/map（哈希表，无序）。注意迭代器失效问题。

填空时注意语法完整性：分号、括号匹配、函数参数类型和个数、返回值类型。

【考点】二分查找答案｜有序矩阵线性扫描｜二分边界处理

🎯 考纲定位 GESP 五级「排序与查找」模块，二分查找是核心考点。命题人卡住的是考生对「二分搜索对象」的混淆——很多人习惯二分下标，却忘了这里二分的是值域。

🧠 解题思维 kthSmallest 本质是二分答案：在值域 [matrix[0][0], matrix[n-1][n-1]] 上二分。countLE(mid) 统计 ≤ mid 的元素个数，用 O(n) 线性扫描实现：从左下角出发，若 matrix[i][j] ≤ x 则该列上方 i+1 个元素均 ≤ x，向右移动；否则向上移动。二分逻辑与数组相同：若 countLE(mid) ≥ k，说明答案 ≤ mid，收右半段 hi = mid；反之收左半段 lo = mid + 1。循环直至 lo == hi 即为答案。

🪤 陷阱拆解

• A 项两处都跳过 mid：若答案恰为 mid 会永远丢失。
• B 项两处都等于 mid：搜索区间不收缩，死循环。
• D 项收左半段写 hi = mid + 1：区间反而扩大，逻辑相反。
• C 项「hi = mid; lo = mid + 1」是唯一符合二分答案的写法。
• 边界陷阱：mid 计算用 lo + (hi - lo) / 2 防溢出；当 countLE(mid) == k 时仍要 hi = mid，因为答案可能等于 mid。

🔄 反命题思维 改题：矩阵仅行有序、列无序，则 countLE 需暴力扫描，复杂度升至 O(n²)，二分仍成立但效率下降。若把 countLE 换成优先队列取出 k 小，则整体 O(k log n)，适合 k 很小的场景。刷到同类题先问：二分的是下标还是值？条件满足时该收哪一侧？