算法练习篇之：丑数-阿南达文事网

算法练习篇之：丑数

- 题目描述
- 解题思路
- 代码实现
- 总结

题目描述

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

解题思路

我们只求丑数，不要去管非丑数。每个丑数必然是由小于它的某个丑数乘以2，3或5得到的，这样我们把求得的丑数都保存下来，用之前的丑数分别乘以2，3，5，找出这三这种最小的并且大于当前最大丑数的值，即为下一个我们要求的丑数。这种方法用空间换时间，时间复杂度为O(n)。（也就是我们需要去维护三个数组，这三个数组分别是质因子为2,3,5的数组，本题中用三个索引去替代，每次我们都将上一次记录的三个索引对应的数字分别乘以对应三个不同的质因子，求出最小的加入到丑数数组中，对于那个被选中的加到数组中的索引我们对其进行更新！）
对于一给定的素数集合 S = {p1, p2, …, pK},考虑一个正整数集合，该集合中任一元素的质因数全部属于S。这个正整数集合包括，p1、p1p2、p1p1、p1p2p3…(还有其它)。该集合被称为S集合的“丑数集合”。

代码实现

去博客设置页面，选择一款你喜欢的代码片高亮样式，下面展示同样高亮的 代码片.

public class getUglyNumbers {//求出丑数（质因子只能包含2,3,5的数）public int UglyNumber(int index){if (index<=0){return 0;}if (index==1){return 1;//1就是最小的丑数}int t2=0,t3=0,t5=0;//变相记录质因子为2,3,5的三个数组，// 每次丑数，都要从三个数组中选出最小的（说是数组，在这里就是索引）int[] res=new int[index];//存放n个丑数的数组res[0]=1;//1就是最小丑数for (int i=1;i<index;i++){res[i]=Math.min(res[t2]*2,Math.min(res[t3]*3,res[t5]*5));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];}public static void main(String[] args) {getUglyNumbers test=new getUglyNumbers();int uglynum=test.UglyNumber(9);System.out.println(uglynum);}}

总结

本题来源于面试经典教材《剑指offer》中归属于其他类型题目。
同许多在算法道路上不断前行的人一样，不断练习，修炼自己！
如有博客中存在的疑问或者建议，可以在下方留言一起交流，感谢各位！
最后，感谢AIAS！

觉得本博客有用的客官，可以给个赞鼓励下！嘿嘿

算法练习篇之：丑数