【每日算法Day 83】邻居小孩一年级就会的乘法表，你会吗？

godweiyang

发布于 2020-04-02 11:38:11

4100

发布于 2020-04-02 11:38:11

文章被收录于专栏：算法码上来

题目链接

LeetCode 668. 乘法表中第k小的数[1]

题目描述

几乎每一个人都用乘法表。但是你能在乘法表中快速找到第小的数字吗？

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

示例1

输入：
m = 3, n = 3, k = 5
输出：
3
解释：
乘法表:
1	2	3
2	4	6
3	6	9
第5小的数字是 3 (1, 2, 2, 3, 3).

示例2

输入：
m = 2, n = 3, k = 6
输出：
6
解释：
乘法表:
1	2	3
2	4	6
第6小的数字是 6 (1, 2, 2, 3, 4, 6).

说明：

和的范围在之间。
的范围在之间。

题解

二分法

因为数量级是级别的，所以显然不能直接枚举，要想一个对数级别的算法。

对数级别首先想到的肯定是二分了，我们二分第小的数，然后求出乘法表中小于等于的数的数量。如果发现，那就说明这个答案太大了，还可以继续缩小。否则的话答案太小了，得增大一点。

那么对于枚举的答案来说，如何找到乘法表中有多少小于等于它的数呢？我们可以直接从开始枚举，和相乘并且结果小于等于的数有个，当然还有个的限制，所以是个。然后和相乘并且结果小于等于的数有个。依此类推下去，最终和相乘并且结果小于等于的数有个。

所以最终小于等于的个数就可以计算为：

二分法+优化

当然这题计算还可以进行一些优化。

首先第小的数是一定小于等于的，所以我们的二分上界可以定为。

其次注意到当之后，个数一定是，所以只需要枚举到就行了。

然后当时，有，所以这部分的求和结果就是。所以又可以写为：

最后，对于某个，我们会发现如果慢慢增大，某一段连续区间内的值都是不会变的。而最大可以增大到，那么这一段区间内的求和就可以直接算出来：

接着令直接跳转到就可以了，这样就不用慢慢加计算了。要特别注意的是最后不能超过。

理论上这样的计算复杂度是更低的，但是实际运行中速度还不如不加最后一步优化，可能原因是除法操作次数太多了，反而总的操作次数超过了直接遍历计算。

代码

二分法（c++）

class Solution {
public:
    int findKthNumber(int m, int n, int k) {
        int l = 1, r = m*n;
        while (l < r) {
            int mid = l+((r-l)>>1);
            if (enough(mid, m, n, k)) r = mid;
            else l = mid+1;
        }
        return l;
    }

    bool enough(int x, int m, int n, int k) {
        int cnt = 0;
        for (int i = 1; i <= m; ++i) {
            cnt += x/i<n?x/i:n;
        }
        return cnt >= k;
    }
};

二分法+优化（c++）

class Solution {
public:
    int findKthNumber(int m, int n, int k) {
        int l = 1, r = k;
        while (l < r) {
            int mid = l+((r-l)>>1);
            if (enough(mid, m<mid?m:mid, n<mid?n:mid, k)) r = mid;
            else l = mid+1;
        }
        return l;
    }

    bool enough(int x, int m, int n, int k) {
        int cnt = n*(x/n), d = 0;
        for (int i = (x/n)+1; i <= m; i = d+1) {
            d = x/(x/i);
            cnt += (x/i)*((d<m?d:m)-i+1);
        }
        return cnt >= k;
    }
};

二分法（python）

class Solution:
    def findKthNumber(self, m: int, n: int, k: int) -> int:
        def enough(x, m, n, k):
            cnt = 0
            for i in range(1, m+1):
                cnt += x//i if x//i<n else n
            return cnt >= k

        l, r = 1, m*n
        while l < r:
            mid = l+((r-l)>>1)
            if enough(mid, m, n, k): r = mid
            else: l = mid+1
        return l

二分法+优化（python）

class Solution:
    def findKthNumber(self, m: int, n: int, k: int) -> int:
        def enough(x, m, n, k):
            cnt, i, d = n*(x//n), x//n+1, 0
            while i <= m:
                d = x//(x//i)
                cnt += (x//i)*((d if d<m else m)-i+1)
                i = d+1
            return cnt >= k

        l, r = 1, k
        while l < r:
            mid = l+((r-l)>>1)
            if enough(mid, m if m<mid else mid, n if n<mid else mid, k): r = mid
            else: l = mid+1
        return l