组长说外包不能吃零食，平时跟组长打打闹闹的，以为他把我当自己人，直到我伸手去拿魔芋爽，组长说外包不能吃零食

今天我刷到个吐槽：平时跟组长嘻嘻哈哈，感觉自己快被“转正”进自己人名单了，结果人家一句话直接把我直接整懵了——我刚伸手去拿点小零食，组长来一句：“外包别吃零食。”

我觉得这事好笑又扎心。写代码时一起骂需求，到了魔芋爽这里就分阶级了？真要讲规矩也行，那就把规矩写明白：零食访问策略、审批流程、异常处理，别搞临时口头热更新。

要不然下次我也学会了——我不吃，我只是在做接口联调：把零食从袋子里读出来，再写回去。谁懂啊，程序员的手，天生就爱“取数”。

那天晚上，我在工位上正啃外卖，HR丢过来一句话： “东哥，明天来一轮算法面，简单的，乘法表第 k 小那个题。” 我当时嘴里的鸡腿差点掉键盘上：这玩意儿我当年看到是直接暴力算的啊…

先把题意思糊一下：有个 m×n 的乘法表，你能想象小学那张 9×9 口诀表吧，只不过这回是 m 行 n 列，第 i 行第 j 列是 i * j。让你找这里面第 k 小的数。

刚开始我脑子里蹦出来的方案特别朴素： “那就把整张表生成出来，扔一个数组里，排序，拿第 k 个，完事。” 典型的写完能跑，跑完能炸的那种。

脑子一想，m 和 n 要是一上来就是 3 万，那乘法表就是 9e8 个元素，int 数组直接给你干到 OOM，连 GC 都懒得救你。这个方案就属于想都别想那种，只能当段子讲。

我后来想通的那个思路，是真正“程序员思维”：不去生成表，只在数值区间上二分。 就是那个…怎么说呢…反正你就先假装答案在 [1, m * n] 之间，然后在这个区间上做二分搜索，每次猜一个 mid，看乘法表里有多少数 <= mid，如果数量小于 k，说明你猜小了，要往右半边找；反之就往左缩。

关键问题就变成一句话： “给你一个 mid，怎么快速算出乘法表里 <= mid 的有多少个？”

这个地方当时我还愣了一下，趴在工位上拿纸算： 第 1 行是 1,2,3,...,n，能贡献 min(n, mid / 1) 个； 第 2 行是 2,4,6,...,2n，能贡献 min(n, mid / 2) 个； 第 i 行就是一堆 i, 2i, 3i...，最多 min(n, mid / i) 个不超过 mid。

所以对每一行 i，累加一下就行了：

privateintcountLessEqual(int m, int n, int mid){
int count = 0;
for (int i = 1; i <= m; i++) {
// 这一行最多有 n 个数，也不能比 mid / i 多
int c = mid / i;
if (c == 0) break;        // 后面行更大，直接退出，省点命
        count += Math.min(n, c);
    }
return count;
}

这个函数一旦有了，二分就顺着写下去就行了，我当时敲的时候还打错了好几遍，把 left 写成 lft，IDEA 一顿红线骂我。完整代码差不多长这样：

publicintfindKthNumber(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;
}

privateintcountLessEqual(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);
// 小优化：如果已经明显大于等于 k 也可以提前 return
// 但为了通用，这里就不写死 k 了
    }
return count;
}

你要是像我一样爱瞎想一下复杂度的话，这个解法大概就是： 二分那一层是 log(m * n)，每次二分都要扫一圈行，是 O(m)，综合起来差不多 O(m * log(mn))，对于面试官给的那些数据规模，完全够用。

这个题还有人会往“第 k 小”这种字样上死磕，非要用堆，搞个小根堆每次 pop 一个再 push 一个新候选，模拟从左上角往右下角扩散。那个做法也能做，不过实现起来很容易写到自闭，边界条件一堆，还不如这个“值域二分”干净。

我当面试的时候就顺嘴跟面试官说了一句： “我不生成乘法表，只在答案上二分。” 对面沉默了一下，说：“行，写吧。” 写到一半我发现 mid / i 忘了用 Math.min(n, xx) 卡一下，差点当场翻车…

总之这题的核心就两件小事： 一个是把“找第 k 小”转成“在数值区间里二分”； 另一个是那个 countLessEqual 的小算发，按行数一算就出来了。

行了不说了，我外卖又凉了，等会儿热一下接着改 bug 去了。