当前位置：首页 > news >正文

丑数问题，力扣264，坑点

news 来源：原创 2024/9/20 5:35:50

丑数问题，力扣264，坑点

力扣链接
给你一个整数 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 通常被视为丑数。
正确源码：

class Solution {public  static int nthUglyNumber(int n) {int p2=1;int p3=1;int p5=1;int[] ugly=new int[n+1];ugly[1]=1;for(int i=2;i<=n;i++){ugly[i]=Math.min(Math.min(3*ugly[p3],5*ugly[p5]),2*ugly[p2]);if(ugly[i]==2*ugly[p2]){p2++;}if(ugly[i]==3*ugly[p3]){p3++;}if(ugly[i]==5*ugly[p5]){p5++;}}return ugly[n];}
}

解读：
可以看出任何一个丑数都必定是前面的某一个比他小的丑数，乘以2或者3或者5得到的
因此只需要把所求丑数之前的所有丑数乘以2，3，5，然后找最小的即可
例如：最开始是求第二个丑数
在这里插入图片描述
2最小

然后是第三个丑数
在这里插入图片描述
3最小，第三个丑数是3
接着是第四个丑数

4最小，第四个丑数是4
这样做下去肯定是可以找到第n个丑数的，可是，是不是太复杂了，时间复杂度非常大
因此进行优化
首先，很明显丑数是递增的
因此在下面的图中
在这里插入图片描述

下一个丑数是5，他是5乘以某一个丑数得到的，10和15和20都是5乘以某一个丑数

但是在5没有被排好之前。是不可能轮到他们的，因为丑数是递增的数列，因此把他们乘出来，就是无用功，所以就可以拿一个指针p5来记录5乘到哪一个丑数了

对于其他因子2和3也是同理，一旦乘了某个丑数，对应的指针就加加

ugly[i]=Math.min(Math.min(3*ugly[p3],5*ugly[p5]),2*ugly[p2]);if(ugly[i]==2*ugly[p2]){p2++;}else if(ugly[i]==3*ugly[p3]){p3++;}else if(ugly[i]==5*ugly[p5]){p5++;}

坑点：下面的代码是错的

class Solution {public  static int nthUglyNumber(int n) {int p2=1;int p3=1;int p5=1;int[] ugly=new int[n+1];ugly[1]=1;for(int i=2;i<=n;i++){ugly[i]=Math.min(Math.min(3*ugly[p3],5*ugly[p5]),2*ugly[p2]);if(ugly[i]==2*ugly[p2]){p2++;}else if(ugly[i]==3*ugly[p3]){p3++;}else if(ugly[i]==5*ugly[p5]){p5++;}}return ugly[n];}
}

区别就在于，正确代码用的三个if，错误代码用的是else if。
错误代码过不了，放idea编译器里面发现会产生一些相同的重复丑数。
因为有可能2 $\times$ ugly[p2]与3 $\times$ ugly[p3]与5 $\times$ ugly[p5]这三个中有至少两个相等,
假设是2 $\times$ ugly[p2]和5 $\times$ ugly[p5]相等，这个时候p2和p5都要同时加加
而用else if就只会加一次，所以会有重复的丑数