数字与数学5：丑数

LeetCode263和264是两道关于丑数的问题&＃xff0c;一听名字挺邪乎。看一下要求&＃xff1a;

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

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

示例1&＃xff1a;
输入&＃xff1a;n &＃61; 6
输出&＃xff1a;true
解释&＃xff1a;6 &＃61; 2 × 3
示例2&＃xff1a;
输入&＃xff1a;n &＃61; 14
输出&＃xff1a;false
解释&＃xff1a;14 不是丑数&＃xff0c;因为它包含了另外一个质因数 7 。

LeetCode263是让你判断一个数是不是丑数&＃xff0c;264是让你判断前n个丑数。

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

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

class Solution
public boolean isUgly(int n)
if (n <&＃61; 0) return false;
while (n % 2 &＃61;&＃61; 0) n /&＃61; 2;
while (n % 3 &＃61;&＃61; 0) n /&＃61; 3;
while (n % 5 &＃61;&＃61; 0) n /&＃61; 5;
return n &＃61;&＃61; 1;



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

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

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

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

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

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

class Solution
public int nthUglyNumber(int n)
int[] factors &＃61; 2, 3, 5;
Set seen &＃61; new HashSet();
PriorityQueue heap &＃61; new PriorityQueue();
seen.add(1L);
heap.offer(1L);
int ugly &＃61; 0;
for (int i &＃61; 0; i long curr &＃61; heap.poll();
ugly &＃61; (int) curr;
for (int factor : factors)
long next &＃61; curr * factor;
if (seen.add(next))
heap.offer(next);



return ugly;



这个题还可以使用dp来做&＃xff0c;后面再说。