985、211研究生争相面试，却被一普通二本生逆袭，薪资仅6500元！

我刷到一条HR吐槽：下午连着面了一堆985、211研究生，岗位却是月薪6500的基础活儿，聊到最后，HR反手选了个普通二本。

评论区立马开锅。有网友说：学历是门面，活儿是地基，工资本来就不讲情分。

也有人替二本出头：“会干活就行，别拿学校当滤镜。”我觉得最真实的一句是：“大家不是想卷，是怕被生活按在工位上摩擦。”

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

乘法表中第k小的数

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

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

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

intkthBrute(int m, int n, int k){
List 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 小
publicintfindKthNumber(int m, int n, int k){
int left = 1;
int right = 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 的数有多少个
privateintcountLessEqual(int m, int n, int x){
long cnt = 0;
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 更安全”，对面一般会点点头：嗯，这孩子细。

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 自己跑一下小样例：

publicstaticvoidmain(String[] args){
Test t = new Test;
System.out.println(t.findKthNumber(3, 3, 5));
System.out.println(t.findKthNumber(2, 3, 6));
}

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

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

行了，差不多，就这样吧，我去续杯奶茶了，你可以把这段代码抄进 IDE 自己跑跑看，有 bug 再来抓我。