剑指Offer算法题 39:丑数

>>强大,10k+点赞的 SpringBoot 后台管理系统竟然出了详细教程!

题目描述

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


解题思路

动态规划。根据丑数的性质得知:丑数只有因子2,3,5;因此有“丑数 = 某较小丑数 * 某因子(2,3,5中的某一个)”。设已知长度为n的丑数序列

求第n+1个丑数X(n+1)。根据递推性质,丑数X(n+1)只可能是以下三种情况其中之一(索引a,b,c为未知数):

由于X(n+1)是最接近X(n)的丑数,因此索引a,b,c需满足以下条件:

若索引a,b,c满足以上条件,则可使用递归公式计算下一个丑数X(n+1),其为三种情况中的最小值,即:

因此,可设置指针a,b,c指向首个丑数(即1),循环根据递归公式得到下一个丑数,并每轮将对应指针执行+1操作即可。

剑指Offer算法题 39:丑数

剑指Offer算法题 39:丑数

时间复杂度:O(n);空间复杂度:O(n)

源码

public class Solution {
    public int GetUglyNumber_Solution(int index) {
        //特殊处理
        if(index <= 0){
            return 0;
        }
        
        //动态规划
        //指针a,b,c指向首个丑数
        int a = 0, b = 0, c = 0;
        int[] dp = new int[index];
        dp[0] = 1;
        
        for(int i = 1; i < index; i++){
   
            int n2 = dp[a] *2, n3 = dp[b] * 3, n5 = dp[c] * 5;
            
            //确定接近当前数的丑数
            dp[i] = Math.min(Math.min(n2,n3),n5);
            
            //对应的指针加1即可
            if(dp[i] == n2){
                a++;
            }
            if(dp[i] == n3){
                b++;
            }
            if(dp[i] == n5){
                c++;
            }
        }
        
        return dp[index-1];
    }
}

运行结果

剑指Offer算法题 39:丑数



原文始发于微信公众号(AJCoder):剑指Offer算法题 39:丑数