*[?]Ugly Number II

1、题目名称

Ugly Number II（丑数2：找出第n个丑数）

2、题目地址

https://leetcode.com/problems/ugly-number-ii/

3、题目内容

英文：Write a program to find the n-th ugly number.

中文：写程序找出第n个丑数

说明：丑数具有如下特征：1是丑数，丑数可以表示为有限个2、3、5的乘积

注意：关于“判断指定数字是否为丑数”，请参考Ugly Number（LeetCode #263）

5、一个TLE的方法

一个最容易想到的方法，就是从1开始依次向后判断各自然数是否为丑数，一直判断到第n个丑数，返回第n个丑数的值。这种方法由于充斥了大量的重复计算，效率很低，因此会导致TLE（Time Limit Exceeded）的结果。

Java代码如下：

 1 /**
 2  * 功能说明：LeetCode 263 - Ugly Number
 3  * 开发人员：Tsybius2014
 4  * 开发时间：2015年8月23日
 5  */
 6 public class Solution {
 7      
 8     /**
 9      * 求第N个丑数
10      * @param n
11      * @return 第N个丑数
12      */
13     public int nthUglyNumber(int n) {
14      
15         if (n <= 1) {
16             return 1;
17         }
18  
19         int counter = 0;
20         for (int i = 1; ; i++) {
21              
22             if (isUgly(i)) {
23                 counter++;
24                 if (counter == n) {
25                     return i;
26                 }
27             } 
28         }
29     }
30      
31     /**
32      * 判断数字是否为丑数
33      * @param num 被判断数字
34      * @return true：丑数，false：非丑数
35      */
36     public boolean isUgly(int num) {
37          
38         if (num <= 0) {
39             return false;
40         }
41          
42         while (num % 2 == 0) num /= 2;
43         while (num % 3 == 0) num /= 3;
44         while (num % 5 == 0) num /= 5;
45          
46         if (num == 1) {
47             return true;
48         } else {
49             return false;
50         }
51     }
52 }

6、解题方法

关于如果更加快速有效地找出第n个丑数的问题，网上已经有很多解题方法和大牛的博客可以参考，这里只是简要说明我用的方法：

申请一个长度为n的数组uglyNumbers，用于从小到大顺序存储n个丑数，数组中的首项为1，即第一个丑数为1
设置三个变量idx2、idx3、idx5存储下标，初始值都为0
找出数组uglyNumbers[idx2]*2、uglyNumbers[idx3]*3、uglyNumbers[idx5]*5的最小值，最小值即为下一个丑数，同时更新最小值对应的下标，如果多个数字同时为最小值，则它们的下标都要更新
找到第n个丑数时，循环结束

一段实现此方法的Java代码如下：

 1 /**
 2  * 功能说明：LeetCode 264 - Ugly Number II
 3  * 开发人员：Tsybius2014
 4  * 开发时间：2015年8月23日
 5  */
 6 public class Solution {
 7      
 8     /**
 9      * 求第N个丑数
10      * @param n
11      * @return 第N个丑数
12      */
13     public int nthUglyNumber(int n) {
14          
15         int[] uglyNumbers = new int[n];
16         uglyNumbers[0] = 1;
17 //      System.out.println("uglyNumbers[0]:1");
18          
19         int idx2 = 0;
20         int idx3 = 0;
21         int idx5 = 0;
22  
23         int counter = 1;
24         while (counter < n) {
25  
26 //          System.out.println("-----------");
27 //          System.out.println("idx2:" + idx2 + ";ugly[idx2]:" + uglyNumbers[idx2]);
28 //          System.out.println("idx3:" + idx3 + ";ugly[idx3]:" + uglyNumbers[idx3]);
29 //          System.out.println("idx5:" + idx5 + ";ugly[idx5]:" + uglyNumbers[idx5]);
30 //          System.out.println("idx2:" + idx2 + ";idx3:" + idx3 + ";idx5:" + idx5);
31              
32             int min = minOf(
33                 uglyNumbers[idx2] * 2, 
34                 uglyNumbers[idx3] * 3, 
35                 uglyNumbers[idx5] * 5);
36              
37             if (min == uglyNumbers[idx2] * 2) {
38 //              System.out.println("min==ugly[idx2]*2:" + uglyNumbers[idx2] * 2);
39 //              System.out.println("idx2:" + idx2 + "→" + (idx2 + 1));
40                 idx2++;
41             }
42  
43             if (min == uglyNumbers[idx3] * 3) {
44 //              System.out.println("min==ugly[idx3]*3:" + uglyNumbers[idx3] * 3);
45 //              System.out.println("idx3:" + idx3 + "→" + (idx3 + 1));
46                 idx3++;
47             }
48  
49             if (min == uglyNumbers[idx5] * 5) {
50 //              System.out.println("min==ugly[idx5]*5:" + uglyNumbers[idx5] * 5);
51 //              System.out.println("idx5:" + idx5 + "→" + (idx5 + 1));
52                 idx5++;
53             }
54              
55             uglyNumbers[counter] = min;
56 //          System.out.println("uglyNumbers[" + counter + "]:" + min);
57             counter++;
58         }
59  
60 //      System.out.println("-----------");
61 //      System.out.println("return:" + uglyNumbers[n - 1]);
62          
63         return uglyNumbers[n - 1];
64     }
65      
66     /**
67      * 求三个数字中最小的数字
68      * @param a 数字a
69      * @param b 数字b
70      * @param c 数字c
71      * @return a、b、c中最小的数字
72      */
73     private int minOf(int a, int b, int c) {
74         int temp = a < b ? a : b;
75         return temp < c ? temp : c; 
76     }
77 }

为了方便理解这段代码，我在这段代码里加入了System.out.println函数用于将结果输出到控制台。解除这些注释行，并指定输入的n为15，执行函数时输出到控制台的结果如下：

  1 uglyNumbers[0]:1
  2 -----------
  3 idx2:0;ugly[idx2]:1
  4 idx3:0;ugly[idx3]:1
  5 idx5:0;ugly[idx5]:1
  6 idx2:0;idx3:0;idx5:0
  7 min==ugly[idx2]*2:2
  8 idx2:0→1
  9 uglyNumbers[1]:2
 10 -----------
 11 idx2:1;ugly[idx2]:2
 12 idx3:0;ugly[idx3]:1
 13 idx5:0;ugly[idx5]:1
 14 idx2:1;idx3:0;idx5:0
 15 min==ugly[idx3]*3:3
 16 idx3:0→1
 17 uglyNumbers[2]:3
 18 -----------
 19 idx2:1;ugly[idx2]:2
 20 idx3:1;ugly[idx3]:2
 21 idx5:0;ugly[idx5]:1
 22 idx2:1;idx3:1;idx5:0
 23 min==ugly[idx2]*2:4
 24 idx2:1→2
 25 uglyNumbers[3]:4
 26 -----------
 27 idx2:2;ugly[idx2]:3
 28 idx3:1;ugly[idx3]:2
 29 idx5:0;ugly[idx5]:1
 30 idx2:2;idx3:1;idx5:0
 31 min==ugly[idx5]*5:5
 32 idx5:0→1
 33 uglyNumbers[4]:5
 34 -----------
 35 idx2:2;ugly[idx2]:3
 36 idx3:1;ugly[idx3]:2
 37 idx5:1;ugly[idx5]:2
 38 idx2:2;idx3:1;idx5:1
 39 min==ugly[idx2]*2:6
 40 idx2:2→3
 41 min==ugly[idx3]*3:6
 42 idx3:1→2
 43 uglyNumbers[5]:6
 44 -----------
 45 idx2:3;ugly[idx2]:4
 46 idx3:2;ugly[idx3]:3
 47 idx5:1;ugly[idx5]:2
 48 idx2:3;idx3:2;idx5:1
 49 min==ugly[idx2]*2:8
 50 idx2:3→4
 51 uglyNumbers[6]:8
 52 -----------
 53 idx2:4;ugly[idx2]:5
 54 idx3:2;ugly[idx3]:3
 55 idx5:1;ugly[idx5]:2
 56 idx2:4;idx3:2;idx5:1
 57 min==ugly[idx3]*3:9
 58 idx3:2→3
 59 uglyNumbers[7]:9
 60 -----------
 61 idx2:4;ugly[idx2]:5
 62 idx3:3;ugly[idx3]:4
 63 idx5:1;ugly[idx5]:2
 64 idx2:4;idx3:3;idx5:1
 65 min==ugly[idx2]*2:10
 66 idx2:4→5
 67 min==ugly[idx5]*5:10
 68 idx5:1→2
 69 uglyNumbers[8]:10
 70 -----------
 71 idx2:5;ugly[idx2]:6
 72 idx3:3;ugly[idx3]:4
 73 idx5:2;ugly[idx5]:3
 74 idx2:5;idx3:3;idx5:2
 75 min==ugly[idx2]*2:12
 76 idx2:5→6
 77 min==ugly[idx3]*3:12
 78 idx3:3→4
 79 uglyNumbers[9]:12
 80 -----------
 81 idx2:6;ugly[idx2]:8
 82 idx3:4;ugly[idx3]:5
 83 idx5:2;ugly[idx5]:3
 84 idx2:6;idx3:4;idx5:2
 85 min==ugly[idx3]*3:15
 86 idx3:4→5
 87 min==ugly[idx5]*5:15
 88 idx5:2→3
 89 uglyNumbers[10]:15
 90 -----------
 91 idx2:6;ugly[idx2]:8
 92 idx3:5;ugly[idx3]:6
 93 idx5:3;ugly[idx5]:4
 94 idx2:6;idx3:5;idx5:3
 95 min==ugly[idx2]*2:16
 96 idx2:6→7
 97 uglyNumbers[11]:16
 98 -----------
 99 idx2:7;ugly[idx2]:9
100 idx3:5;ugly[idx3]:6
101 idx5:3;ugly[idx5]:4
102 idx2:7;idx3:5;idx5:3
103 min==ugly[idx2]*2:18
104 idx2:7→8
105 min==ugly[idx3]*3:18
106 idx3:5→6
107 uglyNumbers[12]:18
108 -----------
109 idx2:8;ugly[idx2]:10
110 idx3:6;ugly[idx3]:8
111 idx5:3;ugly[idx5]:4
112 idx2:8;idx3:6;idx5:3
113 min==ugly[idx2]*2:20
114 idx2:8→9
115 min==ugly[idx5]*5:20
116 idx5:3→4
117 uglyNumbers[13]:20
118 -----------
119 idx2:9;ugly[idx2]:12
120 idx3:6;ugly[idx3]:8
121 idx5:4;ugly[idx5]:5
122 idx2:9;idx3:6;idx5:4
123 min==ugly[idx2]*2:24
124 idx2:9→10
125 min==ugly[idx3]*3:24
126 idx3:6→7
127 uglyNumbers[14]:24
128 -----------
129 return:24

reference: http://bookshadow.com/weblog/2015/08/19/leetcode-ugly-number-ii/