题目描述（中等难度）

输出第 个丑数。

解法一 暴力

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

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

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

下边是当时的代码。

  1. public int countPrimes(int n) {
  2.     boolean[] notPrime = new boolean[n];
  3.     int count = 0;
  5.         if (!notPrime[i]) {
  6.             count++;
  7.             //将当前素数的倍数依次标记为非素数
  8.             for (int j = 2; j * i < n; j++) {
  9.             }
  10.         }
  11.     }
  12.     return count;
  13. }

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

解法二

参考 这里。

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

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

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

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

  1. public int nthUglyNumber(int n) {
  2.     Queue<Long> queue = new PriorityQueue<Long>();
  3.     int count = 0;
  4.     long result = 1;
  6.     while (count < n) {
  7.         result = queue.poll();
  8.         while (!queue.isEmpty() && result == queue.peek()) {
  9.             queue.poll();
  10.         }
  11.         count++;
  12.         queue.offer(result * 2);
  13.         queue.offer(result * 3);
  14.         queue.offer(result * 5);
  15.     }
  16.     return (int) result;
  17. }

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

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

解法三

参考 -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...。

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

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

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

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

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

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

总

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

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

添加好友一起进步~

如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 查看详情