欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数字与数学5:丑数

程序员文章站 2022-03-09 13:40:37
...

LeetCode263和264是两道关于丑数的问题,一听名字挺邪乎。看一下要求:

给你一个整数 n ,请你判断 n 是否为 丑数 。如果是,返回 true ;否则,返回 false 。

丑数 就是只包含质因数 2、3 和/或 5 的正整数。

示例1:
输入:n = 6
输出:true
解释:6 = 2 × 3

示例2:
输入:n = 14
输出:false
解释:14 不是丑数,因为它包含了另外一个质因数 7 。

LeetCode263是让你判断一个数是不是丑数,264是让你判断前n个丑数。

如果 n 不是正整数(即小于等于 0):必然不是丑数,直接返回 false。如果 n是正整数:我们对 n执行 2 3 5 的整除操作即可,直到 nn 被除干净,如果 nn 最终为 1 说明是丑数,否则不是丑数。

这里有一点需要想明白,2 3 5 先除哪一个都是可以的,因为乘法本身具有交换律。所以代码就是:

class Solution {
    public boolean isUgly(int n) {
        if (n <= 0) return false;
        while (n % 2 == 0) n /= 2;
        while (n % 3 == 0) n /= 3;
        while (n % 5 == 0) n /= 5;
        return n == 1;
    }
}

第二个题,我们可以通过一个个计算 ,然后遍历来寻找,但是这样的问题也很明显 ,那就是计算次数太多了,效率不高。

一般涉及到固定n的时候,都要考虑一下能否使用堆来实现,而且遵循”找第K小用大,找第大用小“的原则,这里是要找第K大,所以我们就尝试用最小堆试一下。

初始时堆为空。首先将最小的丑数 11 加入堆。

每次取出堆顶元素 xx,则 xx 是堆中最小的丑数,由于 2x, 3x, 5x2x,3x,5x 也是丑数,因此将 2x, 3x, 5x2x,3x,5x 加入堆。

上述做法会导致堆中出现重复元素的情况。为了避免重复元素,可以使用哈希集合去重,避免相同元素多次加入堆。

在排除重复元素的情况下,第 n 次从最小堆中取出的元素即为第 n个丑数。

class Solution {
    public int nthUglyNumber(int n) {
        int[] factors = {2, 3, 5};
        Set<Long> seen = new HashSet<Long>();
        PriorityQueue<Long> heap = new PriorityQueue<Long>();
        seen.add(1L);
        heap.offer(1L);
        int ugly = 0;
        for (int i = 0; i < n; i++) {
            long curr = heap.poll();
            ugly = (int) curr;
            for (int factor : factors) {
                long next = curr * factor;
                if (seen.add(next)) {
                    heap.offer(next);
                }
            }
        }
        return ugly;
    }
}

这个题还可以使用dp来做,后面再说。