LeetCode: 264. Ugly Number II
题目描述
Write a program to find the n-th ugly number.
Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.
Example:
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.
Note:
- 1 is typically treated as an ugly number.
- n does not exceed 1690.
解题思路
每个 ugly number 乘以 2,3,5 之后还是 ugly number, 1
是 ugly number。
AC 代码
class Solution {
public:
int nthUglyNumber(int n) {
vector<int> uglyNumbers{1};
pair<int, int> ugly2{0, 2}, ugly3{0, 3}, ugly5{0, 5};
int cnt = 1;
while(cnt < n)
{
if(ugly2.second <= ugly3.second && ugly2.second <= ugly5.second)
{
uglyNumbers.push_back(ugly2.second);
}
else if(ugly3.second <= ugly2.second && ugly3.second <= ugly5.second)
{
uglyNumbers.push_back(ugly3.second);
}
else
{
uglyNumbers.push_back(ugly5.second);
}
if(ugly2.second == uglyNumbers.back())
{
++ugly2.first;
ugly2.second = uglyNumbers[ugly2.first]*2;
}
if(ugly3.second == uglyNumbers.back())
{
++ugly3.first;
ugly3.second = uglyNumbers[ugly3.first]*3;
}
if(ugly5.second == uglyNumbers.back())
{
++ugly5.first;
ugly5.second = uglyNumbers[ugly5.first]*5;
}
++cnt;
}
return uglyNumbers.back();
}
};