在LintCode上刷题时遇到了一道比较基础的问题。
丑数：设计一个算法，找出只含素因子2，3，5的第n小的数。
符合条件的数如：1, 2, 3, 4, 5, 6, 8, 9, 10, 12...
我们可以认为1也是一个丑数。
要求时间复杂度为 O(nlogn) 或者 O(n)。
比如输入9，那么输出的应该是第9个丑数，也就是10。
比较直观的思路就是从1开始递增，判断当前数字是否为符合条件的丑数，如果是的话，count就加1，当count等于输入时，输出当前的丑数就是答案。判断一个数是否是丑数并不难，只要将这个数中所有的2，3，5都除净，结果为1就是丑数，不为1就说明这个数有别的因子，就不是丑数。
对应的C++代码如下：
class Solution {
public:
/**
* @param n: An integer
* @return: return a integer as description.
*/
int nthUglyNumber(int n) {
// write your code here
int i=0;
int current_num=0;
int count=0;
while(count<n){
i++;
current_num=i;
while(current_num%2==0)
current_num=current_num/2;
while(current_num%3==0)
current_num=current_num/3;
while(current_num%5==0)
current_num=current_num/5;
if(current_num==1)
count++;
}
return i;
}
};
这个方法可以得到正确结果，但是明显不符合时间复杂度为 O(nlogn) 或者 O(n)的要求。实际提交代码的时候也会因为超时而无法通过。
考虑使用动态规划解决这个问题，后续会更新。
