[每日一题]264. Ugly Number II

求第n个丑数: 动态规划和堆。...

Write a program to find the 

n

-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 

2, 3, 5

. For example, 

1, 2, 3, 4, 5, 6, 8, 9, 10, 12

 is the sequence of the first 

10

 ugly numbers.

Note that 

1

 is typically treated as an ugly number, and n does not exceed 1690.本题是求“丑数”的第二道题，难度中等。其相关的第一道题是丑数判断，也是我们昨天做的题目，难度是简单。丑数的判断比较简单，就是去因子法：不断的除以2、3、5，如果最后的结果等于 1， 那么这个数就叫做丑数。



本题是求第 n 个丑数，这次一共提交了4个方案：暴力法、动态规划、堆和数学方法。暴力法

暴力法是最容易想到的方法：从 1 开始，不停的递增。判断当前的数是否为丑数：如果是则 n  - 1 ；如果不是则循环到下一位。返回 n = 1 的丑数即可。

暴力法会超时，因为有很多重复计算。在判断 8 的时候，我们需要不停的除以 2、3、5。 其实我们不需要计算这么多步骤，因为 4 是丑数， 并且 4 * 2 = 8 ， 所以 8 也一定是丑数。



动态规划

本题的动态规划算法有点复杂：因为第 n 个丑数不是与 第 n - 1 个丑数有关，而是与 前 n - 1 中的某三个丑数相关。

根据丑数的定义，我们可以得出一个结论：除 1 以外，其余的丑数一定是 2、3 或者 5 的倍数。也可以这么说，第 n 个丑数一定大于第 n - 1 个丑数，并且等于 前 n - 1 个丑数分别乘以 2、3 和 5 的最小值。

举个例子，假设我们求的是第 10 个丑数的值。那么前 9 个丑数分别是 1， 2， 3， 4， 5， 6， 8， 9，10。

那么第 10 个丑数一定是如下集合中大于 10 的最小值：

1. 乘以 2 的集合:  12 ( 6 x 2 = 12), 16 ，18， 20
2. 乘以 3 的集合：12 ( 4 x 3 = 12), 15, 18 ...
3. 乘以 5 的集合：15 ( 3 x 5 = 15), 20, 25 ...

所以，结果应该是 12 。

上面的例子，我们其实不需要从 1 开始计算 x 2 的值，我们只需要记录上一个2的倍数 的位置就行了。因为当前的丑数，一定是大于 上一个2的倍数乘以 2。 很容易证明：假设当前的丑数小于上一个2的倍数 乘以 2 ， 那么根据我们的推论，上次应该选择这个丑数。这与假设矛盾。同理可以证明3和5 也只需要保存上一次的倍数的坐标。

咳咳，是真的有点绕，我就是想表达的更清楚一些，说的有点多。这个方法有点像我们以前总结的用数组记录位置的方法：数组元素保存的是上一次操作的位置，这样下次操作的时候，只需要取下一个位置就行。

如果由伙伴有更清晰的解答和描述麻烦评论留言，谢谢。

描述一下动态规范算法的思路:

1. 新建一个Set ，用于存入丑数
[list=1]
2. 此处如果用数组，需要考虑去重的问题。由上面的例子可以看出 12 是 2， 3的倍数，在计算的过程中会出现两次。

[*]新建三个指针p2, p3, p5, 分别指向 2 的倍数，3 的倍数 和 5 的倍数的位置，其实位置都是 0

[/*][*]从 丑数 1 开始计算

[/*]

1. 获取 p2 * 2 , p3 * 3, p5 * 5 中的最小值作为当前丑数
2. 如果当前的丑数是 2 的倍数，则 p2 +1
3. 如果当前的丑数是 3 的倍数，则 p3 +1
4. 如果当前的丑数是 5 的倍数，则 p5 +1

[*]当 Set 中的丑数个数等于 n 时结束循环

[/*][/list]时间复杂度和空间复杂度分别等于 O(N)。



堆

思路是利用最小堆的特性，获取当前最小的丑数，分别乘以 2、3、5，这样可以保证不会遗漏任何丑数。证明： 假设存在一个数是丑数，但是不是前面如何一个数乘以 2、3或者5得到的。那么，这个数于丑数的定义矛盾。所以，不可能存在这样的丑数。

思路：

1. 新建一个最小堆，并将1存入最小堆
2. pop 堆中的最小值， 分别乘以 2、3、5， 并存入 heap 中，并且 n - 1
3. 循环步骤 2
4. 返回当 n = 0 时的弹出的最小值

时间复杂度是 O(N*lgN) ， 空间复杂度是 3*O(N) 。

注意：这个方法需要考虑数据溢出的问题，所以需要先将数转换成 Long ，最后在转换会 Integer 。



该方案由 4群的 @不染 提供， 非常感谢！

他的代码用了比较多的技巧：heap 取最小值，Hash 去重，Array 存结果。



@vic 的代码更简洁，清晰一些。



数学



说明：空间复杂度应该是 O(N)；在 if 判断的时候，做了去重判断，所以，不需要考虑重复的问题了。后台回复“我要刷题”，跟我们一起每天学习算法！Java











5群 @JOKER 的提交



C++





Python









Swift





Ruby



C语言

    关注 一个技术人员的胡言乱语