从HR招聘吐槽到算法面试：二分查找巧解乘法表第k小数

最近在网上看到一位HR的吐槽：下午连着面试了一堆985、211的研究生，岗位却只是个月薪6500的基础活儿，聊到最后，HR反手选了个普通二本毕业生。

评论区立马炸开了锅。有网友说：学历是门面，活儿是地基，工资本来就不讲情分。也有人替二本生出头：“会干活就行，别拿学校当滤镜。”我觉得最扎心的一句是：“大家不是想卷，是怕被生活按在工位上摩擦。”

作为一个程序员，看完只能叹气：HR选二本也不稀奇，能上手、沟通顺、稳定靠谱，有时候比“论文引用数”更值钱。你说疯狂吧，确实疯狂，毕竟6500也得交房租、吃饭、还花呗。

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

那天有个小伙伴发来一个问题：东哥，乘法表里第 k 小的数你会不会？我当时正端着奶茶，差点一口喷键盘上——这不就是那种“看起来是小学数学，其实是进阶算法”的经典题目嘛。

先脑补一下，一个 m 行 n 列的乘法表，第 i 行第 j 列是 i * j，就跟小学黑板上的九九乘法表一样，只是放大版。面试官问你：第 k 小的是多少？很多人第一反应就是“老老实实全算一遍呗”，然后…内存爆炸，时间超时，人也麻了。

我一开始也是这么蠢搞的，写了个最直男版：

int kthBrute(int m, int n, int k) {
    List<Integer> all = new ArrayList<>();
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            all.add(i * j);
        }
    }
    Collections.sort(all);
    return all.get(k - 1);
}

这种写法在面试里顶多算“会写 for 循环”，离“会算法”还挺远。m、n 要是上到 3e4 这种级别，你 new 的这个 list 本身就能把你打回原形。

那怎么办？你会发现一个很有意思的点：对一个固定的 x，你能不能快速算出来“乘法表里 ≤ x 的数字有多少个”？如果能算，并且 x 越大这个数量就越大，那不就一个很标准的“答案上二分”模板么。

你看第 i 行是：i, 2i, 3i, ... , n*i。在这一行里，小于等于 x 的个数，其实就是 min(n, x / i) 这么多（整除就行）。所以整张表里：

count(x) = sum_{i = 1..m} min(n, x / i)

这个 count(x) 是单调不减的，x 越大，<= x 的数只会更多不会少。那第 k 小的数就是“最小的那个 x，使得 count(x) >= k”。

这时候就该把二分查找的刀拿出来磨一磨了。代码大概长这样：

// 在 m x n 的乘法表里，找第 k 小
public int findKthNumber(int m, int n, int k) {
    int left = 1;           // 乘法表里最小就是 1*1
    int right = m * n;      // 粗暴一点，最大就是 m*n

    while (left < right) {
        int mid = left + (right - left) / 2;
        if (countLessEqual(m, n, mid) >= k) {
            // mid 已经够“多”了，答案在 mid 左边（含 mid）
            right = mid;
        } else {
            // 还不够 k 个，说明要放大
            left = mid + 1;
        }
    }
    return left;
}

// 统计乘法表里 <= x 的数有多少个
private int countLessEqual(int m, int n, int x) {
    long cnt = 0; // 小心溢出，虽然一般 k 不至于多到爆 long
    for (int i = 1; i <= m; i++) {
        // 这一行最多 n 个，再多也没有
        int add = Math.min(n, x / i);
        if (add == 0) {
            // 后面行号更大，x/i 只会更小，可以直接 break
            break;
        }
        cnt += add;
    }
    // 这里强转回 int 就行，调用方只拿来和 k 比较
    return (int) cnt;
}

这个代码我是现场敲的，你们不要拿着跟网上模板对着抄哈，变量名、逻辑我都有小改的，起码不是复制粘贴的那一挂。

顺手说两句坑点，免得你在面试官面前当场表演翻车：

1. right = m * n 这行，有人会纠结会不会溢出。一般题目给的范围不会故意卡你 int 溢出，但你要是强迫症，可以写成：

   int right = m * n; 
   // 或者 long r = 1L * m * n; 然后最后强转

   面试里嘴上提一句“这里其实可以开到 long 更安全”，对面一般会点点头：嗯，这孩子细。

2. countLessEqual 里我用了 long cnt，因为 i 从 1 加到 m，单行最多 n 个，m * n 理论上上去以后是可以超过 int 的。虽然实际上 k 也不会大成那样，不过写 long 又不费电，多一层保险嘛。

3. 循环里我加了一个小优化：add == 0 就 break。因为当 x 比 i 还小的时候，这一行就一个都没有，后面行 i+1, i+2…更大，x / i 只会变得更小，没必要再算下去，属于那种“写不写都能过，但写了好看一点”的微优化。

有时候我写这种二分，都喜欢打点 log 看一下收敛过程，特别治愈。你也可以像这样写个 main 自己跑一下小样例：

public static void main(String[] args) {
    Test t = new Test();
    System.out.println(t.findKthNumber(3, 3, 5));  // 期望 3
    System.out.println(t.findKthNumber(2, 3, 6));  // 期望 6
}

顺便吐槽一句，这种题跟很多框架“默认配置”一个德行：你要是傻乎乎暴力上，刚开始还以为挺顺滑的，数据一大立马给你一点颜色看看。之前我写 SpringBoot 默认配置踩坑的时候也是这个感觉，线上一压测，所有“没想清楚的地方”都会连本带利还回来。

最后一个小心态问题哈，很多同学一听“二分答案”就慌，其实你就记住一句话：只要你能把“给定一个值 x，好不好”这个问题写成一个单调的布尔函数，就能套二分模板。乘法表这个题，good(x) 就是 “表里 ≤ x 的数量是不是至少 k 个”，是不是挺自然的。

行了，差不多就这样吧。代码你可以抄进 IDE 跑跑看，有疑问的话，欢迎到 云栈社区 一起讨论。