LEETCODE 1201. Ugly Number III 解题思路分析

题目大意：

丑数 III

请你帮忙设计一个程序，用来找出第 n 个丑数。

丑数是可以被 a 或 b 或 c 整除的 正整数。

示例 1：

输入：n = 3, a = 2, b = 3, c = 5
输出：4
解释：丑数序列为 2, 3, 4, 5, 6, 8, 9, 10… 其中第 3 个是 4。

示例 2：

输入：n = 4, a = 2, b = 3, c = 4 
输出：6 
解释：丑数序列为 2, 3, 4, 6, 8, 9, 12... 其中第 4 个是 6。 

示例 3：

输入：n = 5, a = 2, b = 11, c = 13
输出：10
解释：丑数序列为 2, 4, 6, 8, 10, 11, 12, 13… 其中第 5 个是 10。

示例 4：

输入：n = 1000000000, a = 2, b = 217983653, c = 336916467
输出：1999999984

提示：

• 1 <= n, a, b, c <= 10^9
• 1 <= a * b * c <= 10^18
• 本题结果在 [1, 2 * 10^9] 的范围内

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1201

解题思路分析：

开始并没有想到要利用二分查找来解题，这道题的关键是要求出[1, x]范围内丑数的个数，如果这个个数大于n说明要缩小x，反之就要扩大x的范围。这是典型的二分查找套路。接下来问题就转化为如何求出小于等于x的丑数个数。

对于任意一个正整数x，求出在[1, x]范围内的丑数个数，简单来说应该是：

int count = x / a + x / b + x / c;

但是这个个数并不精确，因为会存在重复的值。比如a=1, b=2, c=3, n=6时：

int count = 6 / 1 + 6 / 2 + 6 / 3; // count = 11
// 这11个数为：
[1, 2, 3, 4, 5, 6] // 6 / 1 = 6
[2, 4, 6] // 6 / 2 = 3
[3, 6] // 6 / 3 = 2

重复的部分应该为每两个数的所有公倍数，因此总数应该减去每两个数间所有公倍数个数，这样公式就进化为：

int count = x / a + x / b + x / c
          - x / lcm(a,b) - x / lcm(a,c) - x / lcm(b,c);

公式中的lcm代表两个数的最小公倍数，x除以最小公倍数即为两数所有公倍数的数量。然而题目到这里还没有结束，我们发现，a和b的公倍数，b和c的公倍数以及a和c的公倍数都包含数字6，当我们将这3个6都排出之后，结果中已经不再存在6了，经过观察发现，数字6为a，b，c这三个数的公倍数，说明三个数的公倍数是不能被删除的，因此结果还要再加上三个数公倍数的个数。至此，最终版本的公式应该为：

int count = x / a + x / b + x / c
          - x / lcm(a,b) - x / lcm(a,c) - x / lcm(b,c)
          +  x / lcm(a,b,c);

注意一点，求三个数的最小公倍数时，应该使用前两个数的最小公倍数与第三个数求解。

最后，我们再啰嗦一下如何求最小公倍数？之前的文章我们多次讲过求解最大公约数的方法，不妨我们在复习一下：

// 求a和b的最大公约数
// 递归方法，用两数相除的余数与两数较小的数继续递归，
// 直到较小的数字变为0，较大数即是结果。
long gcd(long a, long b) {
    if(a > b) return gdc(b, a);
    if (a == 0) return b;
    return gcd(b % a, a);
}

求最小公约数的方法要利用到最大公倍数，其公式为（知识点，要牢记！）：

最小公倍数 = a * b / 最大公约数;

即：

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

以上是本体的核心内容，看下实现代码：

public int nthUglyNumber(int n, int a, int b, int c) {
    long left = 1, right = 2000000000; // 定义左右指针
    long lcmab = lcm(a, b); // a和b的最小公倍数
    long lcmac = lcm(a, c); // a和c的最小公倍数
    long lcmbc = lcm(b, c); // b和c的最小公倍数
    long lcmabc = lcm(lcmab, c); // a和b和c的最小公倍数
    while (left < right) { // 开始二分查找
        long mid = (left + right) / 2; // 计算mid
        // 计算出1到mid之间丑数的个数
        int count = (int) (mid / a + mid / b + mid / c
                         - mid / lcmab - mid / lcmac - mid / lcmbc
                         + mid / lcmabc);
        if (count < n) { // 如果丑数个数小于n
            left = mid + 1; // 扩大搜索范围
        } else { // 反之减小搜索范围
            right = mid;
        }
    }
    return (int)right;
}
// 求a和b的最大公约数
// 递归方法，用两数相除的余数与两数较小的数继续递归，
// 直到较小的数字变为0，较大数即是结果。
long gcd(long a, long b) {
    if(a > b) return gcd(b, a);
    if (a == 0) return b;
    return gcd(b % a, a);
}
// 求a和b的最小公倍数
// 最小公倍数 = a * b / 最大公约数;
long lcm(long a, long b) {
    return a * b / gcd(a, b);
}

本题解法执行时间为0ms。

Runtime: 0 ms, faster than 100.00% of Java online submissions for Ugly Number III.

Memory Usage: 32.8 MB, less than 100.00% of Java online submissions for Ugly Number III.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1201-ugly-number-iii-解题思路分析/