LeetCode 668. 乘法表中第k小的数（数学 + 二分）

给定高度m 、宽度n 的一张 m * n的乘法表，以及正整数k，你需要返回表中第k 小的数字。

这道题首先想到的是有公式，答案都偏向二分，其实题目核心还是一个公式。
有了公式这个模型才会有二分。所以是脑筋急转弯题目。

另外需要记住套路：
涉及元素极多做不到遍历的二维矩阵里的第K小都可以用二分猜答案的套路，转化为“给定一个数，求矩阵中有多少个数比这个数小”，进而实现二分查找。

class Solution:
    def findKthNumber(self, m: int, n: int, k: int) -> int:
        # 对于乘法表中的数字X，它是乘法表中第几小的数字？
        # 求第几小等价于求有多少数字不超过X。

        # 对于X，比X小的数字有
        # smaller_num = [X/1] + [X/2] + ... [X/(X-1)] - (X-1)
        # []为若整数，则不变；若小数，则向上取整

        # 对于X，等于X的数字有
        # equal_num = X%1?1:0 +  X%2?0:1 + ... + X%(X-1)?0:1 + X%X?0:1

        # 如果等于X的数字没有（10*10的乘法表，如13）
        # 则X+1肯定为乘法表内的数字（没有只能为奇数，+1变为偶数则肯定在乘法表内部）
        # 因此可以只二分搜索偶数

        # 因此对于X
        # 可为第(smaller_num + 1) 至 (smaller_num+equal_num)小

        # max(X) = m * n
        # min(X) = 1

        # m * n 为第 m*n 小
        # 1 为第 1 小

        def rank(v):
            smaller_num = 0
            equal_num = 0

            row_num = min(m, v)
            for i in range(1, row_num+1):
                smaller_num += min(math.ceil(v/i) - 1, n)
                if v <= i*n and v % i == 0:
                    equal_num += 1

                # print(':', smaller_num, equal_num)
            return (smaller_num+1, smaller_num+equal_num)


        # 二分搜索
        if k == 1:
            return 1
        elif k == m*n:
            return m*n
        else:
            l = 2
            r = m * n
            if m * n % 2 == 1:
                r -= 1

            l_range = rank(l)
            r_range = rank(r)

            if l == r:
                return l

            while l+2 != r:
                # print('l,r:', l, r)
                if k <= l_range[1]:
                    return l
                elif k >= r_range[0]:
                    return r
                else:
                    mid = (l + r) // 2

                    if mid % 2 == 1:
                        mid += 1

                    # print('mid:', mid)

                    mid_range = rank(mid)

                    if k < mid_range[0]:
                        r = mid
                    elif k > mid_range[1]:
                        l = mid
                    else:
                        return mid

            # l与k相差2
            l_range = rank(l)
            r_range = rank(r)

            if k <= l_range[1]:
                return l
            elif k >= r_range[0]:
                return r
            else:
                return l + 1