剑指offer：丑数

题意描述

把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

解题思路

一、思路一

• 一个丑数的因子只有2,3,5，那么丑数p = 2 ^ x * 3 ^ y * 5 ^ z，换句话说一个丑数一定由另一个丑数乘以2或者乘以3或者乘以5得到，
• 第i个丑数一定是（i-1）个丑数 * （2、3、5）得来，从得到的三个数中，取出最小值，就是第i个丑数
• 可以使用动态规划，求出第（i-1）个丑数，就能求出第i个丑数了。

    public class Solution {
        public int GetUglyNumber_Solution(int index) {
            if(index < 7) return index;	//1-6都是丑数，直接返回
            int[] res = new int[index];	
            res[0] = 1;	//第一个丑数是1
            int t2=0,t3=0,t5=0;
            for(int i=1;i<index;i++){
                //根据第（i-1）个丑数*（2、3、5）的最小值，求出第i个丑数
                res[i] = Math.min(res[t2]*2,Math.min(res[t3]*3,res[t5]*5));
                //不使用else if，因为出现公倍数时，都要+1
                if(res[i] == res[t2]*2) t2++;	
                if(res[i] == res[t3]*3) t3++;
                if(res[i] == res[t5]*5) t5++;
            }
            return res[index-1];
        }
    }

二、思路二

1. 初始化数组array与队列Q2、Q3、Q5
2. 将1插入array
3. 令x为Q2 Q3 Q5中的最小值，将x添加至array尾部，若x存在于
   • Q2：将 x * 2、x * 3、x*5 分别放入Q2 Q3 Q5，从Q2中移除x
   • Q3：将 x * 3、x * 5 分别放入Q3 Q5，从Q3中移除x
   • Q5：将 x * 5放入Q5，从Q5中移除x

    import java.util.*;
    public class Solution {
        public int GetUglyNumber_Solution(int index) {
            if(index < 7) return index;
            Queue<Integer> q2 = new LinkedList<>();
            Queue<Integer> q3 = new LinkedList<>();
            Queue<Integer> q5 = new LinkedList<>();
            q2.add(1);
            int minVal = 0;
            for(int i=0;i<index;i++){
                int v2 = q2.isEmpty() ? Integer.MAX_VALUE : q2.peek();
                int v3 = q3.isEmpty() ? Integer.MAX_VALUE : q3.peek();
                int v5 = q5.isEmpty() ? Integer.MAX_VALUE : q5.peek();
                minVal = Math.min(v2,Math.min(v3,v5));
                if(minVal == v2){
                    q2.poll();
                    q2.add(minVal * 2);
                    q3.add(minVal * 3);
                }else if(minVal == v3){
                    q3.poll();
                    q3.add(minVal * 3);
                }else{
                    q5.poll();
                }
                q5.add(minVal * 5);
            }
            return minVal;
        }
    }	

使用ArrayList也能达到相同效果

    public class Solution {
            public int GetUglyNumber_Solution(int n) {
                if (n <= 0) return 0;
                ArrayList<Integer> list = new ArrayList<Integer>();
                list.add(1);
                int i2 = 0, i3 = 0, i5 = 0;
                while (list.size() < n)//循环的条件
                {
                    int m2 = list.get(i2) * 2;
                    int m3 = list.get(i3) * 3;
                    int m5 = list.get(i5) * 5;
                    int min = Math.min(m2, Math.min(m3, m5));
                    list.add(min);	//比较m2、m3、m5，找出最小值，加入list
                    if (min == m2) i2++;
                    if (min == m3) i3++;
                    if (min == m5) i5++;
                }
                return list.get(list.size() - 1);
            }
        }	

剑指offer：丑数

原文：https://www.cnblogs.com/le-le/p/12853744.html