【面试题34】丑数

【题目描述】

我们把只包含因子2,3和5的数称作丑数，求按从小到大的顺序的第1500个丑数。

例如6,8都是丑数，但是14不是，因为它包含因子7。

习惯上，我们把1当做第一个丑数。

【解决方案】

解法一：逐个判断，直观但不够高效

我的代码实现，仅供参考：

 1         public static int GetUglyNumber(int num)
 2         {
 3             if (num <= 0)
 4                 return 0;
 5 
 6             int result = 0, count = 0;
 7 
 8             while (count < num)
 9             {
10                 result++;
11 
12                 if (IsUglyNumber(result))
13                     count++;
14             }
15 
16             return result;
17         }
18 
19         public static bool IsUglyNumber(int num)
20         {
21             while (num % 2 == 0)
22                 num /= 2;
23 
24             while (num % 3 == 0)
25                 num /= 3;
26 
27             while (num % 5 == 0)
28                 num /= 5;
29 
30             return num == 1 ? true : false;
31         }

解法二：创建数组保存已经找到的丑数，空间换时间

我的代码实现，仅供参考：

 1         public static int GetUglyNumber(int index)
 2         {
 3             if (index <= 0)
 4                 return 0;
 5 
 6             int[] arr = new int[index];
 7             int nextIndex = 1;
 8             int index2 = 0;
 9             int index3 = 0;
10             int index5 = 0;
11             arr[0] = 1;
12 
13             while (nextIndex < index)
14             {
15                 int min = Min(arr[index2] * 2, arr[index3] * 3, arr[index5] * 5);
16                 arr[nextIndex] = min;
17 
18                 while (arr[index2] * 2 <= arr[nextIndex])
19                     index2++;
20 
21                 while (arr[index3] * 3 <= arr[nextIndex])
22                     index3++;
23 
24                 while (arr[index5] * 5 <= arr[nextIndex])
25                     index5++;
26 
27                 nextIndex++;
28             }
29 
30             return arr[nextIndex - 1];
31         }
32 
33         public static int Min(int a, int b, int c)
34         {
35             int min = a > b ? b : a;
36 
37             return min > c ? c : min;
38         }