题目链接
LeetCode 668. 乘法表中第k小的数[1]
题目描述
示例1
输入：m = 3, n = 3, k = 5输出：3解释：乘法表:1 2 32 4 63 6 9第5小的数字是 3 (1, 2, 2, 3, 3).
示例2
输入：m = 2, n = 3, k = 6输出：6解释：乘法表:1 2 32 4 6第6小的数字是 6 (1, 2, 2, 3, 4, 6).
说明：
题解
二分法
二分法+优化
二分法（c++）
classSolution { public: intfindKthNumber(intm, intn, intk) { intl=1, r=m*n; while (l<r) { intmid=l+((r-l)>>1); if (enough(mid, m, n, k)) r=mid; elsel=mid+1; } returnl; } boolenough(intx, intm, intn, intk) { intcnt=0; for (inti=1; i<=m; ++i) { cnt+=x/i<n?x/i:n; } returncnt>=k; } };
二分法+优化（c++）
classSolution { public: intfindKthNumber(intm, intn, intk) { intl=1, r=k; while (l<r) { intmid=l+((r-l)>>1); if (enough(mid, m<mid?m:mid, n<mid?n:mid, k)) r=mid; elsel=mid+1; } returnl; } boolenough(intx, intm, intn, intk) { intcnt=n*(x/n), d=0; for (inti= (x/n)+1; i<=m; i=d+1) { d=x/(x/i); cnt+= (x/i)*((d<m?d:m)-i+1); } returncnt>=k; } };
二分法（python）
classSolution: deffindKthNumber(self, m: int, n: int, k: int) ->int: defenough(x, m, n, k): cnt=0foriinrange(1, m+1): cnt+=x//iifx//i<nelsenreturncnt>=kl, r=1, m*nwhilel<r: mid=l+((r-l)>>1) ifenough(mid, m, n, k): r=midelse: l=mid+1returnl
二分法+优化（python）
classSolution: deffindKthNumber(self, m: int, n: int, k: int) ->int: defenough(x, m, n, k): cnt, i, d=n*(x//n), x//n+1, 0whilei<=m: d=x//(x//i) cnt+= (x//i)*((difd<melsem)-i+1) i=d+1returncnt>=kl, r=1, kwhilel<r: mid=l+((r-l)>>1) ifenough(mid, mifm<midelsemid, nifn<midelsemid, k): r=midelse: l=mid+1returnl
参考资料
[1]
LeetCode 668. 乘法表中第k小的数: https://leetcode-cn.com/problems/kth-smallest-number-in-multiplication-table/
作者简介：godweiyang，知乎同名，华东师范大学计算机系硕士在读，方向自然语言处理与深度学习。喜欢与人分享技术与知识，期待与你的进一步交流~
