每日算法之丑数

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，则说明没有其他的因数，否则则有其他因数，那么他就不是一个丑数
  

问题
当输入数过大时，需要的时间会很长，所以此方法不行
代码

1. package mid.JZ49丑数;
3. import java.util.ArrayList;
5. public class Solution {
6.     public int GetUglyNumber_Solution(int index) {
7.         int current = 1;
8.         ArrayList<Integer> res = new ArrayList<>();
9.         res.add(1);
10.         while(true) {
11.             if (res.size() == index) {
12.                 return res.get(res.size() - 1);
13.             }
15.             current++;
17.             if (check(current)) {
18.                 res.add(current);
19.             }
20.         }
21.     }
22.     public boolean check(int num) {
23.         while(num % 2 == 0) num /= 2;
24.         while(num % 3 == 0) num /= 3;
25.         while(num % 5 == 0) num /= 5;
26.         return num == 1;
27.     }
29.     public static void main(String[] args) {
30.         System.out.println(new Solution().GetUglyNumber_Solution(1500));
31.     }
32. }

复制代码

方法2

思路

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

代码

[code]package mid.JZ49丑数;public class Solution {    public int GetUglyNumber_Solution(int index) {        if (index