丑数
题目 丑数
思路分析
将生成丑数的过程看作是从三个序列中选取最小值进行合并的过程，这三个序列分别是：
- 由已知丑数乘以2得到的序列。
- 由已知丑数乘以3得到的序列。
- 由已知丑数乘以5得到的序列。
这样做的原因是任何一个丑数都可以通过前一个丑数乘以2、3或5得到。我们从1开始（1被视作第一个丑数），然后通过乘以2、3、5生成后续的丑数，并保持这些丑数是有序的。
- 初始化三个指针
index2、index3、index5，分别代表三个序列即将乘以2、3、5的丑数的位置，开始时都指向第一个丑数。 - 每次计算三个序列
index2 * 2、index3 * 3、index5 * 5的值，选择最小的那个作为新的丑数，加入到丑数序列中。 - 如果选中的是哪个序列的值，则将该序列对应的指针加1。这表示我们用这个序列当前的丑数已经生成了下一个丑数，需要移动到下一个丑数继续进行生成。
- 重复步骤2、3，直到找到第n个丑数为止。
这样，每次我们都从三个选项中选出最小的那个，保证了丑数的顺序。同时，每个丑数都是由前面的某个丑数通过乘以2、3或5得到的，确保了这确实是一个丑数。
代码实现
class Solution {
public:
int getUglyNumber(int n) {
if(n<=0)
return 0;
vector<int> ugly(n); // 存储丑数的数组
ugly[0]=1;// 第一个丑数是1
int nextidx=1;// 下一个丑数的索引
int *pMultiply2=&ugly[0];// 指向数组的指针，初始时都指向第一个丑数
int *pMultiply3=&ugly[0];
int *pMultiply5=&ugly[0];
while(nextidx<n){
//从三个数组中找出最小的丑数加入
int minval=min({*pMultiply2*2,*pMultiply3*3,*pMultiply5*5});
ugly[nextidx]=minval;
//更新对应序列的指针
while(*pMultiply2*2<=ugly[nextidx])
++pMultiply2;
while(*pMultiply3*3<=ugly[nextidx])
++pMultiply3;
while(*pMultiply5*5<=ugly[nextidx])
++pMultiply5;
++nextidx;
}
return ugly[n-1];
}
};
💬 评论