首页 > 其他 > 详细

LeetCode 668 乘法表中第k小的数

时间:2021-08-08 11:05:11      阅读:17      评论:0      收藏:0      [点我收藏+]

LeetCode 668 乘法表中第k小的数

一开始拍脑袋想先沿着乘法表对角线搜索, 然后发觉元素大小并不是均匀分布, v=x*y若对xy分别搜索则无法控制单一变量

因此直接对v进行二分搜索, 然后以下为拍脑袋证明搜索结果v必定属于乘法表中的元素

cnt(x)表示乘法表搜索区域中<=x的元素个数

默认题目中的k必定有解

则若此时满足cnt(x) = k, 则x ∈ [l, r]

因为cnt(x)范围为整数且在均在乘法表中, 因此从l-1l时, cnt(x)的增量均由乘法表中的元素提供, 且l为其中最大值, 故l为乘法表中的元素

搜索目标为cnt(v) >= k, 取v的最小值

v = l

因此最终搜索结果v为乘法表中的元素

Python3

class Solution:
    def findKthNumber(self, m: int, n: int, k: int) -> int:
        l, r = 1, n*m
        while l < r:
            mid, cnt = l+r >> 1, 0
            for v in (min(mid//i, m) for i in range(1, min(mid, n) + 1)):
                cnt += v
            if cnt < k:
                l = mid + 1
            else:
                r = mid
        return l

LeetCode 668 乘法表中第k小的数

原文:https://www.cnblogs.com/Simon-X/p/15113824.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!