某HR吐槽:下午面试了一堆985、211的研究生只是一个月薪6500的基础岗位，结果最后却要了一个普通二本生，找工作太疯狂了。

那天面试完出来，我整个人都是懵的。面试官最后扔了个题，说“很简单，乘法表里第 k 小的数，你写个函数”。嘴上说简单，手已经在发抖了，你们懂的，就是那种“这要是写暴力肯定要被嫌弃”的场景。

我当时脑子里先闪过的是最土的做法：先把整个 m*n 的乘法表造出来，全部塞进一个数组，排序，取第 k 个，完事儿。思路很感人对不对，就是性能惨不忍睹。你想想，m、n 要是一上来给个 1e5，你数组都开不下，更别说排序了。

我在草稿纸上随手写了个最土版本，长这样：

defkth_smallest_bruteforce(m, n, k):
    nums = []
for i in range(1, m + 1):
for j in range(1, n + 1):
            nums.append(i * j)
    nums.sort()
return nums[k - 1]

这个函数的唯一优点，就是——能跑。缺点呢，也很明显：面试官一看你写两层 for，再来个 sort，心里大概就给你打上“只会 CRUD 的同学”这个标签了，简历直接从 A4 变成废纸回收。

后来我冷静下来想了想，这玩意儿“看起来像数组，但其实更像是一个有序矩阵”。乘法表每一行都是有序的： 第一行：1, 2, 3, 4, … 第二行：2, 4, 6, 8, … 第三行：3, 6, 9, 12, … 只是它不是整体排好序的，所以没法像普通有序数组那样直接二分下标，但我们可以对“值”二分，对吧。

关键点在这：如果我随便猜一个数 mid，我能不能算出来，乘法表里有多少个数 ≤ mid？如果我能算出来一个 count：

• 如果 count >= k，那说明第 k 小的数肯定在 [1, mid] 这个区间里
• 如果 count < k，那说明第 k 小的数一定在 (mid, 最大值]

听起来是不是就有点二分查找那味儿了。

那怎么数 “≤ mid” 的数量呢？这个地方一开始我也卡了一下。后来一想，乘法表里第 i 行其实是：

i, 2i, 3i, …, n*i

这一行里有多少个数 ≤ mid ？就是 mid // i，但别忘了最多就 n 个，所以要取个最小值：min(n, mid // i)。 整个乘法表的数量，就是把 i 从 1 到 m 都算一遍累加一下就行。

于是我在纸上写了个计数函数：

defcount_leq(m, n, mid):
# 统计乘法表中 <= mid 的数字有多少个
    total = 0
for i in range(1, m + 1):
# 这一行最大是 i * n
# 能取到的列数是 mid // i，但不能超过 n
        total += min(n, mid // i)
return total

有了这个 count_leq，二分就很好写了。左边从 1 开始，右边最大就是 m * n（虽然真实答案一般比这小多了，不过这个上界肯定没错）：

defkth_smallest_in_table(m, n, k):
    left, right = 1, m * n
while left < right:
        mid = (left + right) // 2
if count_leq(m, n, mid) >= k:
# mid 已经“太大”或者刚刚好，收缩右边
            right = mid
else:
# 小于等于 mid 的太少了，第 k 小还在右边
            left = mid + 1
return left

这个写完我自己测了几个例子，心里那种“哦豁，终于不是 O(mnlog(mn)) 这么傻了”的安心感就上来了。复杂度差不多是：二分大概 log(mn) 次，每次 count 要扫 m 行，所以是 O(m * log(m*n))，一般数据量都扛得住。

实际上写代码的时候还有几个小坑：

一个是 m、n 谁大谁小。如果你想再抠一点性能，完全可以让 m = min(m, n)，因为你在 count 里是按行遍历的，行数少一点就少一点循环。比如：

defkth_smallest_in_table(m, n, k):
# 优化一下，行数尽量小
if m > n:
        m, n = n, m

    left, right = 1, m * n
while left < right:
        mid = (left + right) // 2
if count_leq(m, n, mid) >= k:
            right = mid
else:
            left = mid + 1
return left

还有一个就是边界。我当时一紧张，把 while left <= right 写上去了，里边又写了 return mid 之类的，调试半天发现，有的用例刚好卡在左闭右闭和左闭右开之间，结果不是大了一点就是小了一点。后来统一用这种套路：

• 区间 [left, right]
• 循环条件 while left < right
• 满足条件就收缩右边 right = mid
• 不满足就 left = mid + 1
• 最后返回 left

这个模板你多写几次，二分焦虑症就会慢慢好一点，真的。

再补一句，像这种题，面试官其实不是在看你会不会“乘法表”，而是看你能不能把一个“隐式有序”的结构，用“值二分”的方式处理掉。以后只要你看到：

• 找第 k 小 / k 大
• 数据太大，不能直接展开
• 但你能快速判断“有多少元素 ≤ x”

这种题，脑子里就可以把“二分答案 + 计数”这套思路调出来用一用。

行了，今天就先唠到这儿，我去给自己续杯咖啡，不然等下再来一道“第 k 大”我估计要直接睡着了。