AlgoPressAppearance
49-丑数
题目描述
https://leetcode.cn/problems/chou-shu-lcof/
我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
示例:
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
说明:
1 是丑数。
n 不超过1690。
注意：本题与主站 264 题相同：https://leetcode.cn/problems/ugly-number-ii/
思路分析
参考 LeetCode 原题 0264-丑数II
为什么要使用3指针? 不难发现，一个丑数总是由前面的某一个丑数 x3 / x5 / x7 得到。 反过来说也是一样的，一个丑数 x3 / x5 / x7 就会得到某一个更大的丑数。
如果把丑数数列叫做 ugly[i]，那么考虑一下三个数列：
1. ugly[0]*3,ugly[1]*3,ugly[2]*3,ugly[3]*3,ugly[4]*3,ugly[5]*3……
2. ugly[0]*5,ugly[1]*5,ugly[2]*5,ugly[3]*5,ugly[4]*5,ugly[5]*5……
3. ugly[0]*7,ugly[1]*7,ugly[2]*7,ugly[3]*7,ugly[4]*7,ugly[5]*7……
上面这个三个数列合在一起就形成了新的、更长的丑数数列。
如果合在一起呢？这其实就是一个合并有序线性表的问题。
定义三个index 分别指向上面三个数列，下一个丑数一定是三个 index 代表的值中最小的那个。然后相应 index++ 即可。
举个例子 初始值 ugly[0]=1; index1=0; index2=0; index3=0
ugly[1]=Min(ugly[index1]*3,ugly[index2]*5,ugly[index3]*7)
=Min(1*3,1*5,1*7)
=3
于是 index1++;
ugly[2]=Min(ugly[index1]*3,ugly[index2]*5,ugly[index3]*7)
=Min(3*3,1*5,1*7)
=5
于是 index2++;
实现代码
csharp
public class Solution {
public int NthUglyNumber(int n) {
int[] dp = new int[n+1];
dp[1] = 1;
//定义三个指针 p2,p3,p5，下一个数就是前面指针对应乘积最小的数，乘完之后，指针下移
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 num = Math.Min(Math.Min(num2,num3),num5);
if(num == num2){
p2++;
}
if(num == num3){
p3++;
}
if(num == num5){
p5++;
}
dp[i] = num;
}
return dp[n];
}
}
复习：20220508
csharp
public class Solution {
public int NthUglyNumber(int n) {
int[] dp = new int[n+1];
dp[1] = 1;
//丑数都是 2,3,5的倍数，定义三个指针，然后对该出的丑数 dp[i] *2 , *3, *5 取最小值继续
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 num = Math.Min(num2,Math.Min(num3,num5));
Console.WriteLine("num2={0},num3={1},num5={2},num={3}",num2,num3,num5,num);
if(num2 == num){
p2++;
}
if(num3 == num){
p3++;
}
if(num5 == num){
p5++;
}
dp[i] = num;
}
return dp[n];
}
}