从“外包禁食”到算法面试：乘法表第k小数二分查找心得

今天我刷到个段子，挺有意思的。说的是平时跟项目组长嘻嘻哈哈打成一片，感觉自己都快被当成团队“自己人”了。结果呢，就在我伸手去拿包魔芋爽的瞬间，组长来了一句：“外包别吃零食。”

这事听着又好笑又有点扎心。写代码的时候能一起吐槽需求，怎么到了零食柜前就突然有了“阶级”划分？要是真有规矩，也行，那就像写技术文档一样，把规矩定明白：零食访问策略、审批流程、异常处理机制都列清楚，别搞临时口头“热更新”啊。

不然下次我也学聪明了——我不吃，我只是在做“接口联调”：把零食从袋子里读出来，再原封不动地写回去。程序员的手，可不就天生爱“取数”嘛。

面试题：乘法表中第k小的数

巧的是，那天晚上我正啃着外卖，HR的消息就弹过来了：“东哥，明天安排一轮算法面试，题目不难，就那个乘法表里找第k小的数。” 我嘴里的鸡腿差点掉键盘上：这题我印象里当年是直接暴力算的，现在真要面，不得好好琢磨一下？

先理清题意：给你一个 m x n 的乘法表，就像小学的九九乘法表那样，第 i 行第 j 列的值是 i * j。现在要从这个表里找出第 k 小的数字。

我脑子里冒出的第一个方案特别“朴实无华且枯燥”：直接把整张表生成出来，塞进一个数组，排序，然后取第 k 个。典型的“写完能跑，跑完能炸”的思路。稍微一想，如果 m 和 n 都是3万，那表里就有9亿个元素，一个 int 数组直接能把内存干爆，GC看了都摇头。所以这方案也就当个段子听听。

真正能用的思路，得有点“程序员思维”：我们不去生成这张庞大的表，而是在数值的区间上做二分查找。简单说，就是假设答案在 [1, m * n] 这个范围里，然后不断地猜一个中间值 mid，接着去计算乘法表里有多少个数 小于等于 这个 mid。如果这个数量小于 k，说明我们猜小了，答案在更大的那边；反之，答案就在更小的那边或者就是 mid 本身。

那么，核心问题就变成了：给定一个 mid，如何快速算出乘法表里小于等于它的数有多少个？

我当时也卡了一会儿，拿张纸开始算：
第1行是 1, 2, 3, ..., n，所有不超过 mid 的数最多有 min(n, mid / 1) 个。
第2行是 2, 4, 6, ..., 2n，所有不超过 mid 的数最多有 min(n, mid / 2) 个。
依此类推，第 i 行的数是 i 的倍数，不超过 mid 的个数就是 min(n, mid / i)。

所以，我们只需要遍历每一行 i，把这些个数累加起来就行了。这里有个小优化：当 mid / i 等于0时，说明这一行最小的数 i 都已经比 mid 大了，后面的行更大，可以直接跳出循环。

写成 Java 函数大概是这样：

private int countLessEqual(int m, int n, int mid) {
    int count = 0;
    for (int i = 1; i <= m; i++) {
        int c = mid / i;
        if (c == 0) break;          // 后面行更大，直接退出，节省计算
        count += Math.min(n, c);
    }
    return count;
}

有了这个“计数”函数，二分查找的逻辑就顺理成章了。我当时敲代码时，还把 left 打成了 lft，被IDE一顿红线警告。完整的解法如下：

public int findKthNumber(int m, int n, int k) {
    int left = 1;
    int right = m * n;  // 注意：这里m*n可能溢出，实际面试中可以用long更安全

    while (left < right) {
        int mid = left + (right - left) / 2;
        int cnt = countLessEqual(m, n, mid);

        if (cnt >= k) {
            // 表示第 k 小的数在 mid 左边（包括 mid）
            right = mid;
        } else {
            // 小于等于 mid 的不够 k 个，答案肯定在右边
            left = mid + 1;
        }
    }
    return left;
}

private int countLessEqual(int m, int n, int mid) {
    int count = 0;
    for (int i = 1; i <= m; i++) {
        int c = mid / i;
        if (c == 0) break;
        count += Math.min(n, c);
        // 小优化：如果count已经明显大于等于k也可以提前返回，这里为了通用性就不写了
    }
    return count;
}

如果你关心复杂度，这个解法大约是：二分查找的层数是 O(log(m*n))，每一层需要遍历 m 行进行计算，所以总复杂度是 O(m * log(mn))。对于常见的面试求职数据规模，这个效率完全够用。

也有人一看到“第k小”就想用堆（优先队列），模拟从小到大的弹出过程。那种方法也能做，但实现起来边界条件较多，容易写乱。相比之下，这种“值域二分”的思路更清晰，代码也更简洁。

我后来在面试中跟面试官说思路：“我不生成乘法表，我只在答案的可能范围内二分猜数，然后验证。” 对面沉默了一下说：“行，写吧。” 写的时候我还差点忘了用 Math.min(n, c) 来限制每行的最大列数，真是惊出一身冷汗。

总结一下，这道算法题的核心就两点：

1. 转换问题：将“找第k小数”转化为“在有序值域上二分查找”。
2. 高效验证：利用乘法表的性质，用 O(m) 的时间快速计算出小于等于某个值的元素个数。

思路清楚了，用Java实现起来就一气呵成。行了，算法复盘完毕，我那个凉了的外卖也该去热一下了，之后还得继续跟我的bug战斗呢。这种从生活槽点到技术思考的跳跃，大概就是我们开发者广场里常有的日常吧。