算法题：寻找丑数
这是一道在订阅的blog上看到的题目，觉得比较有意思，就动手做了一下。
何为丑数?
丑数(Ugly number)是指其因子中只包含2、3、5的整数，类如6、20、36都是丑数，而7、19、28则不是丑数。特别的：1是最小的丑数
题目：求从小大到的情况下第1500个丑数
解题过程：
- 原始解法:
从1开始，判断当前数字是否丑数，不是则跳至下一个数字，是的话下标+1，如果下标增加到指定的数字，则此时对应的数字为要求的丑数。这个解法简单粗暴，可以说毫无技术含量。因为每一个数都要与2、3、5辗转相处，并且要遍历答案之前的每一个自然数，时间复杂度太差。
- 改进解法:
实际上我们可以试图跳过那些不是丑数的自然数，考虑一下丑数是怎么得来的：从1开始，12＝2，13=3，1*5=5，然后从得到的2、3、5继续乘以对应的2、3、5得到新的数字。这样得到的数字都是丑数，因为不可能包含其他的因子。那么我们可以尝试着来构造一个从小到大排列的数组，数组的长度就是我们需要的丑数序号。
接下来的问题是：如何保持数组在构造的过程中是有序的？
假设我们现在有了部分数组，要添加一个新的丑数。新的丑数必然是从已有的数中，分别乘2、3、5之后获得，为保持有序我们只取其中最小的数字，因为这三个数字中间也许还有其他的丑数。实际上这样存在不必要的计算：可能存在一些数字，乘以对应的2、3、5之后也比当前存在的最大丑数要小，而我们只需要乘以2、3、5之后比当前最大丑数大的那个数。所以，对应2、3、5这三个因子，我们应该保存三个位置，使得这三个位置上的数字乘以对应的2、3、5之后比当前最大丑数大。怎么找？很简单，每次插入新的丑数之后，我们更新一下这三个数的位置就可以了。下一次就对这三个位置的数字分别乘以2、3、5，找出最小的插入数组。这样我们就保证了数组有序，并尽量减少了不必要的计算。
C++代码实现:
#include <iostream>
int get_min_number(int a, int b, int c)
{
int min_ab = std::min(a,b);
return std::min(min_ab, c);
}
int find_ugly_number(int target)
{
if (target < 1)
return 0;
int* array = new int[target];
array[0] = 1;
int *pos2 = array;
int *pos3 = array;
int *pos5 = array;
int index = 1;
while (index < target)
{
int cur_max = get_min_number(*pos2*2, *pos3*3,*pos5*5);
array[index++] = cur_max;
while (*pos2*2 <= cur_max)
pos2++;
while (*pos3*3 <= cur_max)
pos3++;
while (*pos5*5 <= cur_max)
pos5++;
}
int ret = array[target-1];
delete [] array;
return ret;
}
int main()
{
int index = 1500;
int result = find_ugly_number(index);
std::cout << result << std::endl;
return 0;
}
代码也被我放在我Github的issues库中，点击查看
