题目描述（中等难度）

输出第 n 个丑数。

解法一 暴力

判断每个数字是否是丑数，然后数到第 n 个。

public int nthUglyNumber(int n) { int count = 0; int result = 1; while (count < n) { if (isUgly(result)) { count++; } result++; } //result 多加了 1 return result - 1; } public boolean isUgly(int num) { if (num <= 0) { return false; } while (num % 2 == 0) { num /= 2; } while (num % 3 == 0) { num /= 3; } while (num % 5 == 0) { num /= 5; } return num == 1; } 

不过题目没有那么简单，这样的话会超时。

受到 204 题 求小于 n 的素数个数的启发，我们这里考虑一下筛选法。先把当时的思路粘贴过来。

用一个数组表示当前数是否是素数。

然后从 2 开始，将 2 的倍数，4、6、8、10 ...依次标记为非素数。

下个素数 3，将 3 的倍数，6、9、12、15 ...依次标记为非素数。

下个素数 7，将 7 的倍数，14、21、28、35 ...依次标记为非素数。

在代码中，因为数组默认值是 false ，所以用 false 代表当前数是素数，用 true 代表当前数是非素数。

下边是当时的代码。

public int countPrimes(int n) { boolean[] notPrime = new boolean[n]; int count = 0; for (int i = 2; i < n; i++) { if (!notPrime[i]) { count++; //将当前素数的倍数依次标记为非素数 for (int j = 2; j * i < n; j++) { notPrime[j * i] = true; } } } return count; } 

这里的话，所有丑数都是之前的丑数乘以 2, 3, 5 生成的，所以我们也可以提前把后边的丑数标记出来。这样的话，就不用调用 isUgly 函数判断当前是否是丑数了。

public int nthUglyNumber(int n) { HashSet<Integer> set = new HashSet<>(); int count = 0; set.add(1); int result = 1; while (count < n) { if (set.contains(result)) { count++; set.add(result * 2); set.add(result * 3); set.add(result * 5); } result++; } return result - 1; } 

但尴尬的是，依旧是超时，悲伤。然后就去看题解了，分享一下别人的解法。

解法二

参考 这里。

看一下解法一中 set 的方法，我们递增 result，然后看 set 中是否含有。如果含有的话，就把当前数乘以 2, 3, 5 继续加到 set 中。

因为 result 是递增的，所以我们每次找到的其实是 set 中最小的元素。

所以我们不需要一直递增 result ，只需要每次找 set 中最小的元素。找最小的元素，就可以想到优先队列了。

还需要注意一点，当我们从 set 中拿到最小的元素后，要把这个元素以及和它相等的元素都删除。

public int nthUglyNumber(int n) { Queue<Long> queue = new PriorityQueue<Long>(); int count = 0; long result = 1; queue.add(result); while (count < n) { result = queue.poll(); // 删除重复的 while (!queue.isEmpty() && result == queue.peek()) { queue.poll(); } count++; queue.offer(result * 2); queue.offer(result * 3); queue.offer(result * 5); } return (int) result; } 

这里的话要用 long，不然的话如果溢出，可能会将一个负数加到队列中，最终结果也就不会准确了。

我们还可以用是 TreeSet ，这样就不用考虑重复元素了。

public int nthUglyNumber(int n) { TreeSet<Long> set = new TreeSet<Long>(); int count = 0; long result = 1; set.add(result); while (count < n) { result = set.pollFirst(); count++; set.add(result * 2); set.add(result * 3); set.add(result * 5); } return (int) result; } 

解法三

参考 这里-Java-solution)。

我们知道丑数序列是 1, 2, 3, 4, 5, 6, 8, 9...。

我们所有的丑数都是通过之前的丑数乘以 2, 3, 5 生成的，所以丑数序列可以看成下边的样子。

1, 1×2, 1×3, 2×2, 1×5, 2×3, 2×4, 3×3...。

我们可以把丑数分成三组，用丑数序列分别乘 2, 3, 5 。

乘 2: 1×2, 2×2, 3×2, 4×2, 5×2, 6×2, 8×2,9×2,… 乘 3: 1×3, 2×3, 3×3, 4×3, 5×3, 6×3, 8×3,9×3,… 乘 5: 1×5, 2×5, 3×5, 4×5, 5×5, 6×5, 8×5,9×5,… 

我们需要做的就是把上边三组按照顺序合并起来。

合并有序数组的话，可以通过归并排序的思想，利用三个指针，每次找到三组中最小的元素，然后指针后移。

当然，最初我们我们并不知道丑数序列，我们可以一边更新丑数序列，一边使用丑数序列。

public int nthUglyNumber(int n) { int[] ugly = new int[n]; ugly[0] = 1; // 丑数序列 int index2 = 0, index3 = 0, index5 = 0; //三个指针 for (int i = 1; i < n; i++) { // 三个中选择较小的 int factor2 = 2 * ugly[index2]; int factor3 = 3 * ugly[index3]; int factor5 = 5 * ugly[index5]; int min = Math.min(Math.min(factor2, factor3), factor5); ugly[i] = min;//更新丑数序列 if (factor2 == min) index2++; if (factor3 == min) index3++; if (factor5 == min) index5++; } return ugly[n - 1]; } 

这里需要注意的是，归并排序中我们每次从两个数组中选一个较小的，所以用的是 if...else...。

这里的话，用的是并列的 if , 这样如果有多组的当前值都是 min，指针都需要后移，从而保证 ugly 数组中不会加入重复元素。

总

解法二的话自己其实差一步就可以想到了。

解法三又是先通过分类，然后有一些动态规划的思想，用之前的解更新当前的解。