题目描述
题目：把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
输入输出
- 1 --> 1
- 10 --> 12
- 400 --> 311040
- 1500 --> 859963392
方法一
思路
动态规划方法，假设这个数为 n， 如果n是丑数，只有三种可能：
-
n是能整除2，即n % 2 == 0，且n/2是丑数。 -
n % 3 == 0且n/3是丑数。 -
n % 5 == 0且n / 5是丑数。
三种可能只要满足其中一种，就可以确认是丑数了。
代码
使用dp[i]表示i是否为丑数。由于不知道第index个丑数到底是第几个数，所以使用vector保存。
class Solution {
public:
int GetUglyNumber_Solution(int index) {
if(index <= 6) // 1...6都是丑数
return index;
vector<bool> dp(7,true);
int count = 6;
int i = 7; //从数字7开始判断
while(1){
dp.push_back(false); // 默认第i个不是丑数
if(i%2 == 0 && dp[i/2]) {
dp[i] = true;
count++;
}
else if(i%3 == 0 && dp[i/3]) {
dp[i] = true;
count++;
}
else if(i%5 == 0 && dp[i/5]) {
dp[i] = true;
count ++;
}
if(count == index)
break;
i++; // 判断下一个数是不是丑数
}
return i;
}
};
结果
用小数据测试了一下，看起来挺正确的，但是提交发现，过不了，原因是内存超限:您的程序使用了超过限制的内存 。
反思一下，当求第1500个丑数的时候，确实内存太大了。于是想办法优化了下内存。
方法二
思路
为了优化内存，只能想办法不存储所有的数了，而是用一个集合存储所有的丑数，如果要求第n个丑数，也就最多使用n个存储空间。而判断一个数是不是丑数的方法就是判断该数在不在这个集合中。
为了查找的快速，选择使用c++11的unordered_set容器。
代码
class Solution {
public:
int GetUglyNumber_Solution(int index) {
if( index == 1)
return 1;
unordered_set <int> mp;
mp.insert(1); // 1是丑数
int count = 1;
int i = 2;
while(1){
// 能整除2， 且 i/2在丑数集合中
if(i%2 == 0 && mp.find(i/2)!=mp.end()) {
mp.insert(i); //是丑数。添加到集合中
count++;
}
else if(i%3==0 && mp.find(i/3)!=mp.end()) {
mp.insert(i);
count++;
}
else if(i%5==0 && mp.find(i/5)!=mp.end()) {
mp.insert(i);
count ++;
}
if(count == index)
break;
i++;
}
return i;
}
};
结果
内存确实优化了，却还是没过!!! 这次是 运行超时:您的程序未能在规定时间内运行结束，请检查是否循环有错或算法复杂度过大。想了半天也没能再优化下去，只得看看参考答案了。
方法三--最终方案
思路
其实还是同样的思路，不过换了个角度。如果已知了n个丑数，第n+1个丑数必然是前面的某个丑数乘以2，或者乘以3，或者乘以5。至于是谁，就是都尝试一下，取最小。
举个栗子：
现在已知6个丑数 1 2 3 4 5 6， 求第7个丑数。
可以翻译成：假设dp[i]表示第i个丑数的数值，已知丑数的个数为count=6，且前6个丑数 dp[1]=1;dp[2]=2;dp[3]=3;dp[4]=4;dp[5]=5;dp[6]=6; 求dp[7]。
则dp[7]可能有三种情况：
- 从
i=1开始按顺序求v = dp[i]*2，当v>dp[6]，可以停止，则第4个丑数乘2得到的8可能是第7个丑数。 - 从
i=1开始按顺序求v = dp[i]*3，当v>dp[6]，可以停止，则第3个丑数乘3得到的9可能是第7个丑数。 - 从
i=1开始按顺序求v = dp[i]*5，当v>dp[6]，可以停止，则第3个丑数乘5得到的10可能是第7个丑数。
取三种情况的最小值，得到8，就是第7个丑数，即dp[7] = 8。
依此类推，可以求得第8个丑数。
注意，这里有个小优化，按顺序搜索的时候并不需要每次都从1开始，只需要从上次搜索的结束点继续搜索就行了。
例如求dp[8]，同样有三种情况：
- 从
i=4开始按顺序求v = dp[i]*2，当v>dp[7]，可以停止，则第5个丑数乘2得到的10可能是第8个丑数。 - 从
i=3开始按顺序求v = dp[i]*3，当v>dp[7]，可以停止，则第3个丑数乘3得到的9可能是第8个丑数。 - 从
i=2开始按顺序求v = dp[i]*5，当v>dp[7]，可以停止，则第2个丑数乘5得到的10可能是第8个丑数。
取三种情况的最小值，得到10，即dp[8] = 9。
代码
class Solution {
public:
int GetUglyNumber_Solution(int index) {
if(index <= 6)
return index;
int start1=1, start2=1, start3 = 1; //搜索起点
vector<int> dp(index+1, 0);
for(int i=1;i<=6;i++)
dp[i] = i;
int count = 6; //当前丑数的最大索引
while(count < index){
//使用*2第一次超过已知的最大丑数 dp[count] 的
for(int i=start1;i<=count;i++){
if(2*dp[i] > dp[count]){
start1 = i; //记录下这个索引，下次从这里开始
break; // 找到第一个大于就停止搜索
}
}
for(int i=start2;i<=count;i++){
if(3*dp[i] > dp[count]){
start2 = i;
break;
}
}
for(int i=start3;i<=count;i++){
if(5*dp[i] > dp[count]){
start3 = i;
break;
}
}
count++;
dp[count] = min(dp[start1]*2, dp[start2]*3);
dp[count] = min(dp[count], dp[start3]*5);
}
return dp[index];
}
};
总结
自己想出来的方法比较复杂，第1500个丑数是859963392，那么，我的方法就得判断859963392前面的所有数到底是不是丑数，时间复杂度很高。
而正确解法，只用遍历前面的1499个丑数，就可以计算出第1500个丑数的值！
