1、题目名称
Ugly Number II（丑数2：找出第n个丑数）
2、题目地址
3、题目内容
英文：Write a program to find the n-th ugly number.
中文：写程序找出第n个丑数
说明：丑数具有如下特征：1是丑数，丑数可以表示为有限个2、3、5的乘积
注意：关于“判断指定数字是否为丑数”，请参考
5、一个TLE的方法
一个最容易想到的方法，就是从1开始依次向后判断各自然数是否为丑数，一直判断到第n个丑数，返回第n个丑数的值。这种方法由于充斥了大量的重复计算，效率很低，因此会导致TLE（Time Limit Exceeded）的结果。
Java代码如下：
/** * 功能说明：LeetCode 263 - Ugly Number * 开发人员：Tsybius2014 * 开发时间：2015年8月23日 */public class Solution { /** * 求第N个丑数 * @param n * @return 第N个丑数 */ public int nthUglyNumber(int n) { if (n <= 1) { return 1; } int counter = 0; for (int i = 1; ; i++) { if (isUgly(i)) { counter++; if (counter == n) { return i; } } } } /** * 判断数字是否为丑数 * @param num 被判断数字 * @return true：丑数，false：非丑数 */ 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; if (num == 1) { return true; } else { return false; } }} 6、解题方法
关于如果更加快速有效地找出第n个丑数的问题，网上已经有很多解题方法和大牛的博客可以参考，这里只是简要说明我用的方法：
-
申请一个长度为n的数组uglyNumbers，用于从小到大顺序存储n个丑数，数组中的首项为1，即第一个丑数为1
-
设置三个变量idx2、idx3、idx5存储下标，初始值都为0
-
找出数组uglyNumbers[idx2]*2、uglyNumbers[idx3]*3、uglyNumbers[idx5]*5的最小值，最小值即为下一个丑数，同时更新最小值对应的下标，如果多个数字同时为最小值，则它们的下标都要更新
-
找到第n个丑数时，循环结束
一段实现此方法的Java代码如下：
/** * 功能说明：LeetCode 264 - Ugly Number II * 开发人员：Tsybius2014 * 开发时间：2015年8月23日 */public class Solution { /** * 求第N个丑数 * @param n * @return 第N个丑数 */ public int nthUglyNumber(int n) { int[] uglyNumbers = new int[n]; uglyNumbers[0] = 1;// System.out.println("uglyNumbers[0]:1"); int idx2 = 0; int idx3 = 0; int idx5 = 0; int counter = 1; while (counter < n) {// System.out.println("-----------");// System.out.println("idx2:" + idx2 + ";ugly[idx2]:" + uglyNumbers[idx2]);// System.out.println("idx3:" + idx3 + ";ugly[idx3]:" + uglyNumbers[idx3]);// System.out.println("idx5:" + idx5 + ";ugly[idx5]:" + uglyNumbers[idx5]);// System.out.println("idx2:" + idx2 + ";idx3:" + idx3 + ";idx5:" + idx5); int min = minOf( uglyNumbers[idx2] * 2, uglyNumbers[idx3] * 3, uglyNumbers[idx5] * 5); if (min == uglyNumbers[idx2] * 2) {// System.out.println("min==ugly[idx2]*2:" + uglyNumbers[idx2] * 2);// System.out.println("idx2:" + idx2 + "→" + (idx2 + 1)); idx2++; } if (min == uglyNumbers[idx3] * 3) {// System.out.println("min==ugly[idx3]*3:" + uglyNumbers[idx3] * 3);// System.out.println("idx3:" + idx3 + "→" + (idx3 + 1)); idx3++; } if (min == uglyNumbers[idx5] * 5) {// System.out.println("min==ugly[idx5]*5:" + uglyNumbers[idx5] * 5);// System.out.println("idx5:" + idx5 + "→" + (idx5 + 1)); idx5++; } uglyNumbers[counter] = min;// System.out.println("uglyNumbers[" + counter + "]:" + min); counter++; }// System.out.println("-----------");// System.out.println("return:" + uglyNumbers[n - 1]); return uglyNumbers[n - 1]; } /** * 求三个数字中最小的数字 * @param a 数字a * @param b 数字b * @param c 数字c * @return a、b、c中最小的数字 */ private int minOf(int a, int b, int c) { int temp = a < b ? a : b; return temp < c ? temp : c; }} 为了方便理解这段代码，我在这段代码里加入了System.out.println函数用于将结果输出到控制台。解除这些注释行，并指定输入的n为15，执行函数时输出到控制台的结果如下：
uglyNumbers[0]:1-----------idx2:0;ugly[idx2]:1idx3:0;ugly[idx3]:1idx5:0;ugly[idx5]:1idx2:0;idx3:0;idx5:0min==ugly[idx2]*2:2idx2:0→1uglyNumbers[1]:2-----------idx2:1;ugly[idx2]:2idx3:0;ugly[idx3]:1idx5:0;ugly[idx5]:1idx2:1;idx3:0;idx5:0min==ugly[idx3]*3:3idx3:0→1uglyNumbers[2]:3-----------idx2:1;ugly[idx2]:2idx3:1;ugly[idx3]:2idx5:0;ugly[idx5]:1idx2:1;idx3:1;idx5:0min==ugly[idx2]*2:4idx2:1→2uglyNumbers[3]:4-----------idx2:2;ugly[idx2]:3idx3:1;ugly[idx3]:2idx5:0;ugly[idx5]:1idx2:2;idx3:1;idx5:0min==ugly[idx5]*5:5idx5:0→1uglyNumbers[4]:5-----------idx2:2;ugly[idx2]:3idx3:1;ugly[idx3]:2idx5:1;ugly[idx5]:2idx2:2;idx3:1;idx5:1min==ugly[idx2]*2:6idx2:2→3min==ugly[idx3]*3:6idx3:1→2uglyNumbers[5]:6-----------idx2:3;ugly[idx2]:4idx3:2;ugly[idx3]:3idx5:1;ugly[idx5]:2idx2:3;idx3:2;idx5:1min==ugly[idx2]*2:8idx2:3→4uglyNumbers[6]:8-----------idx2:4;ugly[idx2]:5idx3:2;ugly[idx3]:3idx5:1;ugly[idx5]:2idx2:4;idx3:2;idx5:1min==ugly[idx3]*3:9idx3:2→3uglyNumbers[7]:9-----------idx2:4;ugly[idx2]:5idx3:3;ugly[idx3]:4idx5:1;ugly[idx5]:2idx2:4;idx3:3;idx5:1min==ugly[idx2]*2:10idx2:4→5min==ugly[idx5]*5:10idx5:1→2uglyNumbers[8]:10-----------idx2:5;ugly[idx2]:6idx3:3;ugly[idx3]:4idx5:2;ugly[idx5]:3idx2:5;idx3:3;idx5:2min==ugly[idx2]*2:12idx2:5→6min==ugly[idx3]*3:12idx3:3→4uglyNumbers[9]:12-----------idx2:6;ugly[idx2]:8idx3:4;ugly[idx3]:5idx5:2;ugly[idx5]:3idx2:6;idx3:4;idx5:2min==ugly[idx3]*3:15idx3:4→5min==ugly[idx5]*5:15idx5:2→3uglyNumbers[10]:15-----------idx2:6;ugly[idx2]:8idx3:5;ugly[idx3]:6idx5:3;ugly[idx5]:4idx2:6;idx3:5;idx5:3min==ugly[idx2]*2:16idx2:6→7uglyNumbers[11]:16-----------idx2:7;ugly[idx2]:9idx3:5;ugly[idx3]:6idx5:3;ugly[idx5]:4idx2:7;idx3:5;idx5:3min==ugly[idx2]*2:18idx2:7→8min==ugly[idx3]*3:18idx3:5→6uglyNumbers[12]:18-----------idx2:8;ugly[idx2]:10idx3:6;ugly[idx3]:8idx5:3;ugly[idx5]:4idx2:8;idx3:6;idx5:3min==ugly[idx2]*2:20idx2:8→9min==ugly[idx5]*5:20idx5:3→4uglyNumbers[13]:20-----------idx2:9;ugly[idx2]:12idx3:6;ugly[idx3]:8idx5:4;ugly[idx5]:5idx2:9;idx3:6;idx5:4min==ugly[idx2]*2:24idx2:9→10min==ugly[idx3]*3:24idx3:6→7uglyNumbers[14]:24-----------return:24
END