Daily LeetCode – day0116 0878. Nth Magical Number

// 0878. Nth Magical Number
class Solution {
    public int nthMagicalNumber(int n, int a, int b) {
        int c = lcm(a, b);
        long left = Math.min(a, b);
        long right = left * n;
        while (left < right) {
            long mid = left + (right - left) / 2;
            long count = mid / a + mid / b - mid / c;
            if (count == n) {
                right = mid;
            } else if (count > n) {
                right = mid;
            } else if (count < n){
                left = mid + 1;
            }
        }
        return (int) (left % (1e9 + 7));
    }

    private int lcm(int a, int b) {
        return a * b / gcd(a, b);
    }

    private int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }
}
学习笔记:
这道题目是一道不容易的题目,很考验基本功。
先用一波数学分析,这样就可以快速求出某个数字是第n个了。
先手是求最大公约数,然后最小公倍数,接下来就是二分查找。
这是向左边界进行搜索的二分查找。


关于樊轶群

一个善良的理想主义者。
此条目发表在每日LeetCode分类目录。将固定链接加入收藏夹。

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注