剑指Offer面试题：29.丑数
一、题目：丑数
题目：我们把只包含因子2、3和5的数称作丑数（Ugly Number）。求按从小到大的顺序的第1500个丑数。例如6、8都是丑数，但14不是，因为它包含因子7。习惯上我们把1当做第一个丑数。
二、两种解决方案
2.1 一一遍历法：时间效率低下
使用遍历法求第k个丑数，从1开始遍历，如果是丑数则count++，直到count=k为止。那么如何判断丑数呢？根据丑数的定义，丑数只有2，3，5这三个因子，那么我们就拿数字除以这三个因子。具体算法如下：
Step1.如果一个数能够被2整除，那么让他继续除以2；
Step2.如果一个数能够被3整除，那么让他继续除以3；
Step3.如果一个数能够被5整除，那么让他继续除以5；
Step4.如果最后这个数变为1，那么这个数就是丑数，否则不是。
根据以上算法实现代码如下：
public int GetUglyNumber(int index) { if (index <= 0) { return 0; } int number = 0; int uglyCount = 0; while (uglyCount < index) { number++; if (IsUgly(number)) { uglyCount++; } } return number; } private bool IsUgly(int number) { while (number % 2 == 0) { number /= 2; } while (number % 3 == 0) { number /= 3; } while (number % 5 == 0) { number /= 5; } return number == 1 ? true : false; }
该算法非常直观，代码也非常简洁，但最大的问题就在于每个整数都需要计算。即使一个数字不是丑数，我们还是需要对它做求余数和除法操作。因此该算法的时间效率不是很高，
2.2 空间换时间法：时间效率较高
根据丑数的定义，我们可以知道丑数可以由另外一个丑数乘以2，3或者5得到。因此我们可以创建一个数组，里面的数字是排好序的丑数，每一个丑数都是前面的丑数乘以2，3或者5得到的。
我们把得到的第一个丑数乘以2以后得到的大于M的结果记为M2。同样，我们把已有的每一个丑数乘以3和5，能得到第一个大于M的结果M3和M5。那么M后面的那一个丑数应该是M2,M3和M5当中的最小值：Min(M2,M3,M5)。比如将丑数数组中的数字按从小到大乘以2，直到得到第一个大于M的数为止，那么应该是2*2=4<M，3*2=6>M，所以M2=6。同理，M3=6，M5=10。所以下一个丑数应该是6。
根据以上思路实现代码如下：
public int GetUglyNumber(int index) { if (index <= 0) { return 0; } int[] uglyNumbers = new int[index]; uglyNumbers[0] = 1; int nextUglyIndex = 1; int multiply2 = 0; int multiply3 = 0; int multiply5 = 0; int min = 0; while (nextUglyIndex < index) { min = Min(uglyNumbers[multiply2] * 2, uglyNumbers[multiply3] * 3, uglyNumbers[multiply5] * 5); uglyNumbers[nextUglyIndex] = min; while (uglyNumbers[multiply2] * 2 <= uglyNumbers[nextUglyIndex]) { multiply2++; } while (uglyNumbers[multiply3] * 3 <= uglyNumbers[nextUglyIndex]) { multiply3++; } while (uglyNumbers[multiply5] * 5 <= uglyNumbers[nextUglyIndex]) { multiply5++; } nextUglyIndex++; } int result = uglyNumbers[index - 1]; uglyNumbers = null; return result; } private int Min(int num1, int num2, int num3) { int min = num1 < num2 ? num1 : num2; min = min < num3 ? min : num3; return min; }
和第一种方案相比，第二种方案不需要在非丑数的整数上做任何计算，因此时间效率有明显提升。但也需要指出，第二种算法由于需要保存已经生成的丑数，因此需要一个数组，从而增加了空间消耗。如果是求第1500个丑数，将创建一个能容纳1500个丑数的数组，这个数组占内存6KB。
三、单元测试与性能对比
3.1 单元测试
（1）测试用例
public static void Main(string[] args) { Program p = new Program(); p.Test(1); p.Test(2); p.Test(3); p.Test(4); p.Test(5); p.Test(6); p.Test(7); p.Test(8); p.Test(9); p.Test(10); p.Test(11); p.Test(1500); p.Test(0); p.Test(1500); Console.ReadKey(); } public void Test(int index) { int result = GetUglyNumberWithSpace(index); Console.WriteLine("Test result is {0}", result); Console.WriteLine("-------------End-------------"); }
（2）测试结果
3.2 性能对比
这里我们使用两种解决方案来求第1500个丑数，通过下面的图片可以清楚地看到两种方案的响应时间。（这里借助老赵的CodeTimer类来进行时间效率的监测）
（1）一一遍历法：65秒，我等得花儿都谢了
（2）空间换时间法：4毫秒，迅雷不及掩耳
由对比可以看出，一个简单的优化，再通过6KB的空间换取了巨大的时间效率，在实际开发中是一个值得实践的解决思路（当然，事先得权衡一下利弊）。
