题目要求:把只包含质因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
前20个丑数为:1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36。
但本题并不是输入一个数让你判断是否是丑数,而是给你索引数,输出索引数对应的丑数
1 import java.lang.Math; 2 import java.util.*; 3 public class Solution { 4 public int GetUglyNumber_Solution(int index) { 5 //考虑特殊情况 6 if(index <= 0) return 0; 7 if(index > 0 && index < 7) return index; 8 int p2 = 0, p3 = 0, p5 = 0; //3个指针pointer 9 //用来存放所有丑数的list 10 //序号实际存储 0 1 2 3 4 5 6 7 8 ,list.get()中用到的,也就是index 11 //实际存储丑数 1 2 3 4 5 6 8 9 10 12 ArrayList<Integer> list=new ArrayList<Integer>(); 13 list.add(1); 14 while(list.size() < index){ 15 int m2=list.get(p2)*2; 16 int m3=list.get(p3)*3; 17 int m5=list.get(p5)*5; 18 int min=Math.min(m2,Math.min(m3,m5)); 19 list.add(min); 20 if(min==m2)p2++; 21 if(min==m3)p3++; 22 if(min==m5)p5++; 23 } 24 return list.get(list.size()-1); 25 } 26 }
通俗易懂的解释:(https://www.nowcoder.com/questionTerminal/6aa9e04fc3794f68acf8778237ba065b来源:牛客网)
原文:https://www.cnblogs.com/shareidea94/p/11119904.html