丑数
把只包含质因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。(点我直接练习)
分析
本体难度偏中等,难点集中在如何建立丑数序列。所以首先要明确丑数的实际含义,它和质数的本质区别在于一个数字能被分解的最小因子是2,3,5就符合了丑数的定义,比如8这个数字可以用2^3来表示,所以8就是丑数。所以从这个定义出发,所有的丑数实际上是用1累成2, 3,5得到的。所以我们声明一个向量(栈也是可以得),初始的丑数实际上是1,其余剩下的所有丑数使用1和2、3、5开始进行累乘获得,但是如果直接这样操作一定会出现大量重复的数字。所以下一步是如何进行添加新丑数且避免不重复的丑数。所以首先声明一个向量,并将1作为第一个数据存入向量,之后的推荐解决办法如下:
1. 同时使用三个指向该向量的指针ptr2,ptr3,ptr5,初始状态同时指向向量的第一个位置;
2. ptr2指针指向的数据只与2进行乘法运算,同理,另外两个指针只和3或5进行乘法运算,取出最小的乘积结果,第一次的乘积结果分别为2、3、5,经过比较,2最小,将2存入向量;
3. 获得该次最小乘积结果的指针向后移,第一次运算的结果中,2是由ptr2指针的乘法运算获得,ptr2向后移,即指向向量中的第二个位置。
4. 重复2,3两个步骤,直到向量中存储了足够数量以满足题目输入的N。
python的解决办法和C++一样,这道题就不再翻译一遍了(其实就是懒)
使用到的知识点
C++
序列构建
Python
暴力法,没什么知识点
题解
C++(Clang++ 3.9) : 运行时间:3ms 占用内存:436k
class Solution {
public:
int GetUglyNumber_Solution(int index) {
if(index<7)
return index;
int NewUglyNum = 1;
int ptr2=0,ptr3=0,ptr5 = 0; //三个队列的指针
vector<int> uglynumbers;
uglynumbers.push_back(NewUglyNum);
while(uglynumbers.size() < index){
//选出三个队列头最小的数
NewUglyNum = min(uglynumbers[ptr2] * 2, min(uglynumbers[ptr3] * 3, uglynumbers[ptr5] * 5));
//这三个if有可能进入一个或者多个,进入多个是三个队列头最小的数有多个的情况
if(uglynumbers[ptr2] * 2 == NewUglyNum) ptr2++;
if(uglynumbers[ptr3] * 3 == NewUglyNum) ptr3++;
if(uglynumbers[ptr5] * 5 == NewUglyNum) ptr5++;
uglynumbers.push_back(NewUglyNum);
}
return NewUglyNum;
}
};