题目：
只包含因子2、3、5的数字被称为丑数。例如4和6是丑数，而14不是丑数，因为含有因子7。习惯上把1作为第一个丑数。求按从小到大顺序的第1500个丑数。
分析：
假设一个丑数顺序数组ugly_nums[],对于其中一个丑数ugly=ugly_nums[x],存在2*ugly_nums[i-1]<=ugly,2*ugly_nums[i]>ugly,也就是说2乘以一个丑数刚刚大于丑数ugly；
同理也存在3*ugly_nums[j-1]<=ugly,3*ugly_nums[j]>ugly，和5*ugly_nums[k-1]<=ugly,5*ugly_nums[k]>ugly。
那么第x+1个丑数应该是3个倍数结果中最小的那个，即ugly_nums[x+1]=min{2*ugly_nums[i],3*ugly_nums[j],5*ugly_nums[k]};
这应该算是一种数值逼近的思想，遇到一些需要计算的数值需找时可以考虑，比如找顺序数组中满足和为某值得数字对
算法需要借助一个辅助数组存储丑数，空间复杂度O(n)。时间复杂度O(n)
代码
int FindUglyNum(unsigned int index)
{
int *uglynums=new int[index];
uglynums[0]=1;
uglynums[1]=2;
uglynums[2]=3;
uglynums[3]=4;
uglynums[4]=5;
unsigned int i=1,j=1,k=1;
unsigned int min_uglynum=0;
unsigned int idx=4;
while (idx<index)
{
if (2*uglynums[i]<uglynums[idx])
{
i++;
}
if (3*uglynums[j]<uglynums[idx])
{
j++;
}
if (5*uglynums[k]<uglynums[idx])
{
k++;
}
min_uglynum=MIN(MIN(2*uglynums[i],3*uglynums[j]),5*uglynums[k]);
uglynums[++idx]=min_uglynum;
}
return uglynums[index-1];
}
原文：http://www.cnblogs.com/wangzaizhen/p/5167015.html