每日算法之丑数(丑数判断)

  本篇文章为你整理了每日算法之丑数(丑数判断)的详细内容,包含有丑数是什么 丑数判断 丑数 leetcode 丑是数字几 每日算法之丑数,希望能帮助你了解 每日算法之丑数。

  我们先看到题目,把只包含质因子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));

  

 

  有了上面的定义我们就可以知道,丑数的形式就是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];

  

 

  以上就是每日算法之丑数(丑数判断)的详细内容,想要了解更多 每日算法之丑数的内容,请持续关注盛行IT软件开发工作室。

郑重声明:本文由网友发布,不代表盛行IT的观点,版权归原作者所有,仅为传播更多信息之目的,如有侵权请联系,我们将第一时间修改或删除,多谢。

留言与评论(共有 条评论)
   
验证码: