我们把只包含质因子 2、3 和 5 的数称作丑数(Ugly Number)。求按从小到大的顺序的第 n 个丑数。
示例:
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
说明:1 是丑数。
n 不超过1690。来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/chou-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
我们使用一个result容器来记录我们从小到大的丑数,默认初始值为1,然后用三个指针分别为two,three,five来记录我们应该对哪个数字进行×2或3或5的操作。同时我们挑出其中最小的那个数作为我们当前的丑数结果。
假设我们当前要求第十个丑数
我们初始的vector中的第0号元素为1
我们的two,three,five全部为0
two
three
five
0
0
0
Vector
0
1
1
然后我们分别用2乘two指针指向的容器中的位置0的数字, 3乘two指针指向的容器中的位置0的数字,5乘two指针指向的容器中的位置0的数字。我们分别得到了2,3,5
从中我们挑选出最小值2,并将其压入vector中,然后将我们two的指针++
two
three
five
1
0
0
Vector
0
1
1
2
然后我们分别用2乘two指针指向的容器中的位置1的数字, 3乘two指针指向的容器中的位置0的数字,5乘two指针指向的容器中的位置0的数字。我们分别得到了4,3,5
从中我们挑选出最小值3,并将其压入vector中,然后将我们three的指针++
two
three
five
1
1
0
Vector
0
1
2
3
4
5
6
7
8
9
1
2
3
然后我们分别用2乘two指针指向的容器中的位置1的数字, 3乘two指针指向的容器中的位置1的数字,5乘two指针指向的容器中的位置0的数字。我们分别得到了4,6,5
从中我们挑选出最小值4,并将其压入vector中,然后将我们two的指针++
two
three
five
2
1
0
Vector
0
1
2
3
4
5
6
7
8
9
1
2
3
4
然后我们分别用2乘two指针指向的容器中的位置2的数字, 3乘two指针指向的容器中的位置1的数字,5乘two指针指向的容器中的位置0的数字。我们分别得到了6,6,5
从中我们挑选出最小值5,并将其压入vector中,然后将我们five的指针++
two
three
five
2
1
1
Vector
0
1
2
3
4
5
6
7
8
9
1
2
3
4
5
然后我们分别用2乘two指针指向的容器中的位置2的数字, 3乘two指针指向的容器中的位置1的数字,5乘two指针指向的容器中的位置1的数字。我们分别得到了6,6,10
从中我们挑选出最小值6,并将其压入vector中,然后将我们two,three的指针++
two
three
five
3
2
1
Vector
0
1
2
3
4
5
6
7
8
9
1
2
3
4
5
6
然后我们分别用2乘two指针指向的容器中的位置3的数字, 3乘two指针指向的容器中的位置2的数字,5乘two指针指向的容器中的位置1的数字。我们分别得到了8,9,10
从中我们挑选出最小值8,并将其压入vector中,然后将我们two的指针++
two
three
five
4
2
1
Vector
0
1
2
3
4
5
6
7
8
9
1
2
3
4
5
6
8
然后我们分别用2乘two指针指向的容器中的位置4的数字, 3乘two指针指向的容器中的位置2的数字,5乘two指针指向的容器中的位置1的数字。我们分别得到了10,9,10
从中我们挑选出最小值9,并将其压入vector中,然后将我们three的指针++
two
three
five
4
3
1
Vector
0
1
2
3
4
5
6
7
8
9
1
2
3
4
5
6
8
9
然后我们分别用2乘two指针指向的容器中的位置4的数字, 3乘two指针指向的容器中的位置3的数字,5乘two指针指向的容器中的位置1的数字。我们分别得到了10,12,10
从中我们挑选出最小值10,并将其压入vector中,然后将我们two,five的指针++
two
three
five
5
3
2
Vector
0
1
2
3
4
5
6
7
8
9
1
2
3
4
5
6
8
9
10
然后我们分别用2乘two指针指向的容器中的位置5的数字, 3乘two指针指向的容器中的位置3的数字,5乘two指针指向的容器中的位置2的数字。我们分别得到了12,12,15
从中我们挑选出最小值12,并将其压入vector中,然后将我们two,three的指针++
two
three
five
6
4
2
Vector
0
1
2
3
4
5
6
7
8
9
1
2
3
4
5
6
8
9
10
12
这样我们就从n-1也就是我们容器下标9的位置得到了我们的结果12。
- class Solution {
- public:
- int nthUglyNumber(int n) {
- int two=0;
- int three=0;
- int five=0;
- vector<int> result;
- result.push_back(1);
- for(int i=1;i
- {
- int n2=result[two]*2;
- int n3=result[three]*3;
- int n5=result[five]*5;
- result.push_back(min(min(n2,n3),n5));
- if(result[i]==n2)
- {
- two++;
- }
- if(result[i]==n3)
- {
- three++;
- }
- if(result[i]==n5)
- {
- five++;
- }
-
- }
- return result[n-1];
- }
- };