264. Ugly Number II
Đề Bài
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
Thuật Toán & Kỹ Thuật
⏱️ Thời gian
O(n)
💾 Không gian
O(n)
Lời Giải
C++
0264-ugly-number-ii.cpp
class Solution {
public:
int nthUglyNumber(int n) {
queue<int> mq;
mq.push(1);
unordered_set<int> visited;
visited.insert(1);
while (!mq.empty()) {
long long num = (long long)mq.front();
mq.pop();
for (int x : {2, 3, 5}) {
if (num*x > INT_MAX) {
continue;
}
if (visited.count(num*x)) {
continue;
}
visited.insert(num*x);
mq.push(num*x);
}
}
vector<int> v(visited.begin(), visited.end());
sort(v.begin(), v.end());
return v[n - 1];
}
};