丑数

最新推荐文章于 2024-11-24 23:52:55 发布

井底的笨鸟

最新推荐文章于 2024-11-24 23:52:55 发布

阅读量308

点赞数

分类专栏：剑指offer

本文链接：https://blog.csdn.net/jingsuwen1/article/details/51674685

版权

剑指offer 专栏收录该内容

42 篇文章

订阅专栏

本文介绍了一个用于寻找第N个丑数（仅包含质因数2、3和5的正整数）的高效算法实现。通过动态规划的方法，确保每次迭代都能找到下一个最小的丑数，并更新对应的指针。文章提供的Java代码实现了这一逻辑，并通过一个min辅助函数简化了比较过程。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目描述

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

多读两边代码就懂了。

public class Solution {
    public int GetUglyNumber_Solution(int index) {
        if(index<=0)
            return 0;
        int []ugly=new int [index];
        ugly[0]=1;
        int nextindex=1;
        int index2=0;
        int index3=0;
        int index5=0;
        while(nextindex<index)
            {
            ugly[nextindex]=min(ugly[index2]*2,ugly[index3]*3,ugly[index5]*5);
            while(ugly[index2]*2<=ugly[nextindex])
                index2++;
            while(ugly[index3]*3<=ugly[nextindex])
                index3++;
            while(ugly[index5]*5<=ugly[nextindex])
                index5++;
            nextindex++;            
        }
        return ugly[nextindex-1];
    }
    
    public int min(int num1,int num2,int num3)
        {
        int a=(num1<num2)?num1:num2;
        int b=(a<num3)?a:num3;
        return b;
    }
}