一、题目
An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.
Given an integer n, return the nth ugly number.
Example 1:
Input: n = 10
Output: 12
Explanation: [1, 2, 3, 4, 5, 6, 8, 9, 10, 12] is the sequence of the first 10 ugly numbers.
Example 2:
Input: n = 1
Output: 1
Explanation: 1 has no prime factors, therefore all of its prime factors are limited to 2, 3, and 5.
Constraints:
1 <= n <= 1690
二、题解
class Solution {
public:
int nthUglyNumber(int n) {
vector<int> res(n+1,0);
res[1] = 1;
for(int i2 = 1,i3 = 1,i5 = 1,i = 2;i <= n;i++){
int a = res[i2] * 2,b = res[i3] * 3,c = res[i5] * 5;
int minValue = min(a,min(b,c));
if(minValue == a) i2++;
if(minValue == b) i3++;
if(minValue == c) i5++;
res[i] = minValue;
}
return res[n];
}
};
