AlgoPressAppearance
0264-丑数II
https://leetcode.cn/problems/ugly-number-ii
给你一个整数 n ，请你找出并返回第 n 个 丑数 。
丑数 就是只包含质因数 2、3 和/或 5 的正整数。
示例 1：
输入：n = 10
输出：12
解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
示例 2：
输入：n = 1
输出：1
解释：1 通常被视为丑数。
提示：
1 <= n <= 1690
基本思路
- 固定输出前5位 [1,2,3,4,5,6]
- 从第六为开始
2*3, 然后2*2*2然后2*5然后2*2*3
参考代码: 错误
打算使用dp[i] 除以丑数，换一个最接近的相乘的方法，但是失败了 ，比如 12 的下一个数是 3*5=15 但是目前个位数的算法不能涵盖 12/6*8 = 16了 这样倒推的方法无法覆盖后面最终的成绩，应该还是从前面往后乘，取最小值
csharp
public class Solution {
public int NthUglyNumber(int n) {
int[] dp = new int[n+1];
for(int i=1; i<=n; i++){
if(i<=6){
dp[i] = i;
}
else{
//计算可以相除的数字
if(dp[i-1] % 12 == 0){
dp[i] = dp[i-1] / 12 * 15;
}
if(dp[i-1] % 9 == 0){
dp[i] = dp[i-1] / 9 * 10;
}
else if(dp[i-1] % 8 == 0){
dp[i] = dp[i-1] / 8 * 9;
}
else if(dp[i-1] % 6 == 0){
dp[i] = dp[i-1] / 6 * 8;
}
else if(dp[i-1] % 5 == 0){
dp[i] = dp[i-1] / 5 * 6;
}
else if(dp[i-1] % 4 == 0){
dp[i] = dp[i-1] / 4 * 5;
}
else if(dp[i-1] % 3 == 0){
dp[i] = dp[i-1] / 3 * 4;
}
else if(dp[i-1] % 2 == 0){
dp[i] = dp[i-1] / 2 * 3;
}
}
//Console.WriteLine("dp[{0}]={1}",i,dp[i]);
}
return dp[n];
}
}
基本思路：官方解法
暴力解法，就是循环到某数 n 之后，知道前一个数，如 10，那么从11开始，依次去用 2,3,5除该数，看是否是丑叔。 该方法简单，但是效率较低
我们知道丑数就是2,3,5相乘的数(除去1)，所以下一个丑数必然是前面某个数 乘以2，或者 乘以3，或者乘以5 得来的 所以，将前面的所有数字都乘以2,3,5，然后取min值就可以了
但是此方法还是会进行很多次多余计算，比如我们计算到4由
2*2得来，那么对于后面的数来说，前面的 1,2再乘以2，就没有意义了这样通过分析，我们知道某个数 乘以2 之后，对于当前的数来说，再也没有去乘并且校验的意义了，因为必然小于后面的数，对于乘以3和乘以5的数有同样的情况
所以这样来说，我们维护3个指针，分别为 p2,p3,p5 ，最开始指向 1, 当后面相乘的时候，一旦某个数相乘是最小值，那么就移动该指针到后面一个数
比如： 到 dp[2] 的时候 是取的 p2*2 的值，所以 p2++，移到2的位置，具体代码如下
一开始，丑数只有{1}，1可以同2，3，5相乘，取最小的1×2=2添加到丑数序列中。
现在丑数中有{1，2}，在上一步中，1已经同2相乘过了，所以今后没必要再比较1×2了，我们说1失去了同2相乘的资格。
现在1有与3，5相乘的资格，2有与2，3，5相乘的资格，但是2×3和2×5是没必要比较的，因为有比它更小的1可以同3，5相乘，所以我们只需要比较1×3，1×5，2×2。
依此类推，每次我们都分别比较有资格同2，3，5相乘的最小丑数，选择最小的那个作为下一个丑数，假设选择到的这个丑数是同i（i=2，3，5）相乘得到的，所以它失去了同i相乘的资格，把对应的pi++，让pi指向下一个丑数即可。
[1,2,3,4,5,6]
参考代码
csharp
public class Solution {
public int NthUglyNumber(int n) {
int[] dp = new int[n+1];
dp[1] = 1;
int p2 = 1;
int p3 = 1;
int p5 = 1;
for(int i=2;i<=n;i++){
int num2 = dp[p2] * 2;
int num3 = dp[p3] * 3;
int num5 = dp[p5] * 5;
int result = Math.Min(Math.Min(num2,num3),num5);
if(result == num2){
p2++;
}
if(result == num3){
p3++;
}
if(result == num5){
p5++;
}
dp[i] = result;
}
return dp[n];
}
}