猫史档案馆

题：

描述：编写一个程序，找出第 n 个丑数。丑数就是只包含质因数 2, 3, 5 的正整数。例如：15是3*5，9是3*3，15和9都是丑数示例:输入: n = 10 输出: 12 解释:1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。 说明:1 是丑数。 n 不超过1690。

由第一个丑数1，分别于三个质因数相乘，得到三个丑数，然后排序，得到1、2、3、5.然后对第二个丑数2，再次进行一步骤的操作，得到丑数4、6、10.升序排列得到1、2、3、4、5、6、10.再对第三个丑数进行一步骤的操作，再对整体的数列进行排序，即可得到新的丑数序列。丑数既然可以通过这种方式获得，针对题目要求，可以进行一些修改，即可得到第k个丑数。

对于第一个质因数，分别和2、3、5相乘，取到最小的2，作为第二个质因数，然后，由于1已经和质因数2相乘得到丑数，这时，1不需要和质因数2再做乘法操作来获取丑数所以，第二次操作，就是1和3、5相乘，而质因数2和第二个丑数相乘，取到最小的3作为第三个丑数，然后，由于1已经和质因数3相乘得到丑数，这时，1不需要和质因数3再做乘法操作来获取丑数所以，第三次操作，就是1和5相乘，而质因数2、3和第二个丑数相乘，取到最小的4作为第四个丑数，然后，由于2已经和质因数2相乘得到丑数，这时，2不需要和质因数2再做乘法操作来获取丑数依次类推，即可依次得到丑数序列。

图片示例，素材来源：网络。

由于需要分别标记质因数2、3、5分别和第几个丑数进行乘法运算，所以，可以定义三个指针对应三个质因数，指向数组中的位置。这样，每次判断出，取到的值是和某个质因数反应，就可以将该质因数对应的指针向后移动一位。

就是丑数原理！