263. Ugly Number的子母题
题目要求输出从1开始数，第n个ugly number是什么并且输出。
一开始想着1遍历到n直接判断，超时了。
class Solution
{
public:
bool isUgly(int num)
{
while (num % == && num > )
num /= ;
while (num % == && num > )
num /= ;
while (num % == && num > )
num /= ;
return num == ;
}
int nthUglyNumber(int n)
{
int res = ;
vector<int> sta;
sta.push_back(res);
while (sta.size() <= n)
{
++res;
if (isUgly(res))
sta.push_back(res);
else
{
while (!isUgly(res))
{
++res;
}
sta.push_back(res);
}
}
for (auto a : sta)
{
cout << a;
}
return sta[n];
}
};
超时以后想通过数组保存ugly数字，然后对其排序，直接输出第n个ugly数字。
这里有点投机取巧的意思。利用static去保存，这样在不同数据测试中，只需要第一次计算保存数据，后面只需要执行返回static里面的值就好了，所以评测结果非常快。
Runtime: 4 ms, faster than 97.70% of C++ online submissions for Ugly Number II.
class Solution
{
public:
int nthUglyNumber(int n)
{
static vector<int> uglyNums;
long long a, b, c, maxN = INT_MAX;
if (uglyNums.empty())
{
for (a = 1; a < maxN; a *= 2)
for (b = a; b < maxN; b *= 3)
for (c = b; c < maxN; c *= 5)
uglyNums.push_back(c);
sort(begin(uglyNums), end(uglyNums));
}
return uglyNums[n - 1];
}
};
最优解里看到的，也是讨论区里面用的最多的一种方法，0ms。
class Solution
{
public:
int nthUglyNumber(int n) {
static vector<int> ugly {};
static int last();
static int c2=, c3=, c5=;
static int i2=, i3=, i5=;
while (ugly.size() < n) {
while (c2 <= last) c2 = * ugly[++i2];
while (c3 <= last) c3 = * ugly[++i3];
while (c5 <= last) c5 = * ugly[++i5];
ugly.push_back(last = min(c2, min(c3, c5)));
}
return ugly[n-];
}
};