什么是丑日寅日(每日算法之丑数)
导读: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版权声明:以上内容作者已申请原创保护,未经允许不得转载,侵权必究!授权事宜、对本内容有异议或投诉,敬请联系网站管理员,我们将尽快回复您,谢谢合作!