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-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , , , 标签。将固定链接加入收藏夹。

LEETCODE 1201. Ugly Number III 解题思路分析》有1条回应

  1. Pingback引用通告: LEETCODE 1231. Divide Chocolate 解题思路分析 - LEETCODE从零刷LEETCODE从零刷

发表评论

您的电子邮箱地址不会被公开。