丑数(java实现)

剑指 Offer 49 丑数

此题与力扣264题相同丑数II

题目说明

我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

1 是丑数。
n 不超过1690。

示例

例1

1
2
3

输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

笔者理解

此题是一道数学规律问题，在力扣题库中被定义为中等题。

解法1

笔者思考此题时，考虑过递归及暴力求解等方法，但效果欠佳，这是通过暴力法预先将2，3，5的多种组合放入结果数组中，然后排序再去相应位置的丑数出来。

public int nthUglyNumber(int n) {
        List <Integer>result = new <Integer>ArrayList();
        //定义一个动态数组用来存储丑数
        int num;
        for(int i=0;i<31;i++){
            for(int j=0;j<21;j++){
                for(int k=0;k<15;k++){
                    //依次求出2，3，5各个组合的质数组合乘积
                    num = (int) ((Math.pow(2,i))*(Math.pow(3,j))*(Math.pow(5,k)));
                    result.add(num);
                }
            }
        }
        Collections.sort(result);
        //排序
        return result.get(n-1);
    }

时间和空间效率都较低，此解法可以通过跳出预知的测试n对应的丑数来减少时间；

解法2

笔者偶然翻阅评论时，发现此题可以用动态规划法做，便仔细思考了以下，又实际去进行了演算，发现此题用动态规划挺合适的。

实际上，包括第一个丑数1，都是由2的i次方 x 3的j次方 x 5的k次方所得，实际上第n个丑数就是求数学表达式的第n个最小值

丑数的递推性质：丑数只包含因子 2,3,5 ，因此有 “丑数 == 某较小丑数× 某因子”

例如：No.1 = 1 ;No.2 = 2 x No.1;No.3 = 3 x No.1(因为3 x No.1小于No.2 x 2);No.4 = No.2 x 2(因为No.2 x 2小于5 x No.1)；

public int nthUglyNumber(int n) {
        int a = 0,b = 0,c = 0;
        //分别定义当前2，3，5各自的运算结果所在下标
        int []result = new int[n];
        //动态规划数组
        result[0] = 1;
        //第一个丑数1
        int temp2,temp3,temp5;
        for(int i=1;i<n;i++){
            temp2 = 2*result[a];
            temp3 = 3*result[b];
            temp5 = 5*result[c];
            result[i] = Math.min(Math.min(temp2,temp3),temp5);
            //存入当前可能的最小值
            if(result[i]==temp2) {
                //乘过一次2后，标记2，下次只能用 上次乘过2的结果 再乘以2 用以比较
                a++;
            }
            if(result[i]==temp3){
                //同上
                b++;
            }
            if(result[i]==temp5){
                //同上
                c++;
            }
        }
        return result[n-1];
    }