首页IT科技什么是丑日寅日(每日算法之丑数)

什么是丑日寅日(每日算法之丑数)

时间2025-08-03 02:05:42分类IT科技浏览5563
导读:JZ49 丑数 题目...

JZ49 丑数

题目

我们先看到题目             ,把只包含质因子2               、3和5的数称作丑数(Ugly Number)             。例如6                   、8都是丑数                       ,但14不是      ,因为它包含质因子7                       。 习惯上我们把1当做是第一个丑数      。

方法1:质因数分解(暴力)

思路

算法实现

一个很朴素的做法 从1~n每次+1         ,一直枚举                       ,直到找到地N个丑数为止 那么还有一个待解决的问题          ,如何判断当前数字是不是丑数呢? 我们总结一下丑数的性质:只能分解为2,3,5的如干次幂相乘的数      ,即设第个丑数为                      ,则 res = 2*x + 3*y + 5*z 那么我们只需要通过质因数分解              ,判断他分解2,3,5后   ,是否为1                     ,如果为1                  ,则说明没有其他的因数,否则则有其他因数                 ,那么他就不是一个丑数

问题

当输入数过大时                      ,需要的时间会很长   ,所以此方法不行

代码

package mid.JZ49丑数; import java.util.ArrayList; public class Solution { public int GetUglyNumber_Solution(int index) { int current = 1; ArrayList<Integer> res = new ArrayList<>(); res.add(1); while(true) { if (res.size() == index) { return res.get(res.size() - 1); } current++; if (check(current)) { res.add(current); } } } public boolean check(int num) { while(num % 2 == 0) num /= 2; while(num % 3 == 0) num /= 3; while(num % 5 == 0) num /= 5; return num == 1; } public static void main(String[] args) { System.out.println(new Solution().GetUglyNumber_Solution(1500)); } }

方法2

思路

有了上面的定义我们就可以知道             ,丑数的形式就是2x3y5z                       ,所以我们可以定义一个数组res      ,存储第n个丑数         。 因为我们要将丑数按从小到大的顺序排序         ,所以我们就得将对应的丑数放在对应的下标位置                       ,小的放前面                       。 这个时候上面我们的出来的丑数的格式就起作用了          ,丑数的形式无非就是这样2x3y5z      ,所以我们就将res[n]去乘以 2        、3            、5                      ,然后比较出最小的那个              ,就是我们当前的下一个丑数了          。

代码

package mid.JZ49丑数; public class Solution { public int GetUglyNumber_Solution(int index) { if (index <= 6) return index; int x = 0, y = 0, z = 0; int[] res = new int[index]; res[0] = 1; for (int i = 1; i < index; i++) { res[i] = Math.min(res[x]*2, Math.min(res[y]*3, res[z]*5)); if (res[i] == res[x]*2) x++; if (res[i] == res[y]*3) y++; if (res[i] == res[z]*5) z++; } return res[index - 1]; } }

创心域SEO版权声明:以上内容作者已申请原创保护,未经允许不得转载,侵权必究!授权事宜、对本内容有异议或投诉,敬请联系网站管理员,我们将尽快回复您,谢谢合作!

展开全文READ MORE
移动无线网能用,但是电视不能看(移动路由器视频播放) seo_网站优化教程(掌握SEO优化,助你网站风生水起)