▶ 三个与丑数相关的问题
▶ 第 263题，判定一个数字是否是丑数，即其素因子是否仅由 2，3，5 构成。
● 常规消除判别，4 ms
class Solution
{
public:
bool isUgly(int num)
{
if (num < )
return false;
for (; !(num % ); num /= );
for (; !(num % ); num /= );
for (; !(num % ); num /= );
return num == ;
}
};
● 递归方法，6 ms
class Solution
{
public:
bool isUgly(int num)
{
if (num < )
return false;
return judge(num);
}
bool judge(int n)
{
if (n < )
return true;
if (!(n % ))
return isUgly(n / );
else if (!(n % ))
return isUgly(n / );
else if (!(n % ))
return isUgly(n / );
return false;
}
};
▶ 第 264 题，计算第 n 个丑数。第 263 题就是个坑，不能用逐个判断的方法来找，否则超时
● 用第 263 题的方法逐个检查，计算 1352 时超时，使用递归法逐个检查也是计算 1352 时超时。
class Solution
{
public:
bool isUgly(int num)
{
if (num < )
return false;
for (; !(num % ); num /= );
for (; !(num % ); num /= );
for (; !(num % ); num /= );
return num == ;
}
int nthUglyNumber(int n)
{
int i, count;
for (i = , count = ; count < n; i++)
{
if (isUgly(i))
count++;
}
return i - ;
}
};
● 筛法，空间开销爆炸，丑数的增长速度远小于自然数的增长速度
class Solution
{
public:
int nthUglyNumber(int n)
{
if (n < )
return n;
vector<bool>table(n * , false);
int i, count;
for (i = ; i < ; table[i++] = true);// 1 ~ 6 都是丑数，table[0] 闲置
for (; i < n * ; i++)
table[i] = !(i % ) && table[i / ] || !(i % ) && table[i / ] || !(i % ) && table[i / ];
for (i = ,count = ; i < n * && count < n; i++)
{
if (table[i])
count++;
}
return i - ;
}
};
● 代码，8 ms，正解，每次从已经有的丑数中选出三个来分别乘以 2，乘以 3，乘以 5，谁最小就收录为新的丑数，同时选取的指针向大端移动一格
class Solution
{
public:
int nthUglyNumber(int n)
{
if (n < )
return n;
vector<int> table(n);
int i, t2, t3, t5;
for (i = table[] = , t2 = t3 = t5 = ; i < n; i++)
{
table[i] = min(table[t2] * , min(table[t3] * , table[t5] * ));
if (table[i] == table[t2] * )
t2++;
if (table[i] == table[t3] * )
t3++;
if (table[i] == table[t5] * )
t5++;
}
return table[n - ];
}
};
● 代码，41 ms，使用优先队列，每次将出队的丑数的 2 倍，3 倍，5 倍分别入队，排在后边备选
class Solution
{
public:
int nthUglyNumber(int n)
{
if (n == )
return ;
priority_queue<int, vector<int>, greater<int>> q;
int i, temp;
for (i = , q.push(); i < n; i++)
{
for (temp = q.top(), q.pop(); !q.empty() && q.top() == temp; q.pop());// 删除队头等值重复
if (temp <= 0x7fffffff / )
q.push(temp * );
if (temp <= 0x7fffffff / )
q.push(temp * );
if (temp <= 0x7fffffff / )
q.push(temp * );
}
return q.top();
}
};
● 代码，计算不超过一个给定的正整数的丑数的个数，再对所求第 n 个丑数进行二分搜索，计算 1600 时超时。
■ 重要的点：
class Solution
{
public:
int nums5(int val)// 计算不超过 val 的正整数中形如 5^p 的数字个数
{
int n = ;
for (n = ; val >= ; n++, val /= );
return n;
}
int nums35(int val)// 计算不超过 val 的正整数中形如 3^q × 5^p 的数字个数
{
int n;
for (n = ; val >= ; n += + nums5(val), val /= );
// 第 k 次循环时向 n 增添 3^(k-1) （一个）及形如 3^(k-1) × 5^p 的数字个数（等价于 val / 3^(k-1) 中形如 5^p 的数字个数）
return n;
}
int nums235(int val)// 计算不超过 val 的正整数中形如 2^r × 3^q × 5^p 的数字个数（丑数个数）
{
int n;
for (n = ; val >= ; n += + nums35(val), val /= );
// 第 k 次循环时向 n 增添 2^(k-1) （一个）及形如 2^(k-1) × 3^q × 5^p 的数字个数（等价于 val / 2^(k-1) 中形如 3^q × 5^p 的数字个数）
return n;
}
int nthUglyNumber(int n)//用二分法查找第 n 个丑数，若 ≤ x 的丑数个数是 n，而 ≤ x - 1 的丑数个数是 n - 1，则 x 就是第 n 个丑数
{
if (n < )
return n;
n--; // 之后的算法中认为 2 是第一个丑数
int valLp, numLp, valRp, numRp, valMp, numMp;
for (valLp = , valRp = , numLp = , numRp = ; numRp < n; valLp = valRp, numLp = numRp, valRp = valLp * , numRp = nums235(valRp));
// 不断扩大扩大搜索范围，使得在 [ valLp, valRp ] 范围内有 [ numLp, numRp ] 个丑数，valRp = 2 × valLp，numLp ≤ n ≤ numRp
if (numRp == n) // 恰好碰到了上限
return valRp;
for(valMp = (valLp + valRp) / ;; valMp = (valLp + valRp) / )
{
numMp = nums235(valMp);
if (valRp == valMp + && numMp == n - && numRp == n)// val 和 num 在 Mp 和 Rp 之间都有跳跃，Rp 即为所求
return valRp;
if (valMp == valLp + && numLp == n - && numMp == n)// val 和 num 在 Lp 和 Mp 之间都有跳跃，Mp 即为所求
return valMp;
if (numMp >= n) // Mp 偏大
valRp = valMp, numRp = numMp;
else // Mp 偏小
valLp = valMp, numLp = numMp;
}
}
};
▶ 第 313 题，扩展丑数，将上述限制条件 “素因子仅由 2，3，5 构成” 改为素因子由一个数组指定，仍然要求第 n 个丑数。
● 代码，31 ms，将上述选最小的方法进行扩展
class Solution
{
public:
int nthSuperUglyNumber(int n, vector<int>& primes)
{
const int m = primes.size();
vector<int> table(n), count(m, );
int i, j, minValue;
for (i = table[] = ; i < n; table[i++] = minValue)
{
for (j = , minValue = 0x7fffffff; j < m; j++)
{
if (minValue > primes[j] * table[count[j]])
minValue = primes[j] * table[count[j]];
}
for (j = ; j < m; j++)
{
if (minValue == primes[j] * table[count[j]])
count[j]++;
}
}
return table[n - ];
}
};
● 大佬的代码，20 ms，基本相同的算法，优化了循环过程
class Solution
{
public:
int nthSuperUglyNumber(int n, vector<int>& primes)
{
vector<int> ugly(n, ), ind(primes.size(), ), val(primes.size(), );
int i, j, next;
for (i = , ugly[] = ; i < n; ugly[i++] = next)
{
for (j = , next = INT_MAX; j < primes.size(); j++)
{
if (val[j] == ugly[i - ])
val[j] = ugly[ind[j]++] * primes[j];
next = next < val[j] ? next : val[j];
}
}
return ugly[n - ];
}
};