leetcode_264. 丑数 II
264. 丑数 II - 力扣（LeetCode）
本来是想像求素数那样子求出丑数 但是发现这个数据量好像有点大 但是 On²
的时间复杂度在10000的数据量还是可以接受的
但是用逆向思维 可以很轻松得到结果
居然已经给出了丑数的因子 那么我们可直接用最小的丑数 * 因子 就可以得到另一个丑数
class Solution {
public:
int nthUglyNumber(int n) {
vector<int> vec = {1};
int a = 0, b = 0, c = 0; //指示数
int num2 = 2, num3 = 3, num5 = 5; //丑数
for ( int i = 1; i < n; ++i ){
num2 = vec[a] * 2;
num3 = vec[b] * 3;
num5 = vec[c] * 5;
vec.push_back( min( min(num2, num3), num5) );
if ( vec.back() == num2 ) ++a;
if ( vec.back() == num3 ) ++b;
if ( vec.back() == num5 ) ++c;
}
return vec.back();
}
};