本文转载自微信公众号《程序员千语》，作者程序员千语。转载本文请联系程序员倩语公众号。力扣：https://leetcode-cn.com/problems/chou-shu-lcof/“GitHub：https://github.com/nateshao/leetcode/blob/main/algo-notes/src/main/java/com/nateshao/sword_offer/topic_36_nthUglyNumber/Solution.java《丑数》题目描述：我们称一个只包含质因数2、3、5的数为丑数。按升序查找第n个丑数。难度：中等示例：输入：n=10输出：12解释：1,2,3,4,5,6,8,9,10,12是前10个丑数。思路：“丑数的递归性：丑数只包含因数2、3、5，所以有‘丑数=某个更小的丑数x子’（例如：10=5x2）。因此，可以设指针a,b,c指向第一个丑数（即1），循环根据递推公式得到下一个丑数，每一轮对对应指针执行+1。复杂度分析：时间复杂度O(N):mediumN=n,动态规划需要遍历计算dplist空间复杂度O(N):一个长度为N的dplist使用0(N)个额外空间packagecom.nateshao.sword_offer.topic_36_nthUglyNumber;/***@dateCreatedby邓通杰on2021/12/1122:54*@微信公众号程序员千语*@个人网站www.nateshao.cn*@bloghttps://nateshao.gitee.io*@GitHubhttps://github.com/nateshao*@Giteehttps://gitee.com/nateshao*说明：丑数*说明：我们称一个只包含质因数2、3、5的数为丑数（UglyNumber）。求o的升序第n个丑数订购。*/publicclassSolution{publicstaticvoidmain(String[]args){System.out.println("nthUglyNumber(10)="+nthUglyNumber(10));//nthUglyNumber(10)=12System.out.println("nthUglyNumber2(10)="+nthUglyNumber2(10));//nthUglyNumber2(10)=12}/***思路：乘以2或3或5，然后比较取最小值。**@paramn*@return*/publicstaticintnthUglyNumber(intn){if(n<=0)return0;int[]arr=newint[n];arr[0]=1;//第一个丑数为1intmultiply2=0,multiply3=0,multiply5=0;for(inti=1;i
