[leetcode] 264. Ugly Number II (medium)

本文主要是介绍[leetcode] 264. Ugly Number II (medium)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

263. Ugly Number的子母题

题目要求输出从1开始数，第n个ugly number是什么并且输出。

一开始想着1遍历到n直接判断，超时了。

class Solution
{
public:bool isUgly(int num){while (num % 5 == 0 && num > 4)num /= 5;while (num % 3 == 0 && num > 2)num /= 3;while (num % 2 == 0 && num > 1)num /= 2;return num == 1;}int nthUglyNumber(int n){int res = 1;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 {1};static int last(1);static int c2=2, c3=3, c5=5;static int i2=0, i3=0, i5=0;while (ugly.size() < n) {while (c2 <= last) c2 = 2 * ugly[++i2];while (c3 <= last) c3 = 3 * ugly[++i3];while (c5 <= last) c5 = 5 * ugly[++i5];ugly.push_back(last = min(c2, min(c3, c5)));}return ugly[n-1];
}
};