题目描述
把只包含质因子2、3和5的数称作丑数（Ugly Number）。
例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
思路:
首先从丑数的定义我们知道，一个丑数的因子只有2,3,5，那么丑数p = 2 ^ x * 3 ^ y * 5 ^ z
那么我们可以理解为每一个数字都是上一个数字×2或者3,5来的
因此我们只需要定义三个数字,i2保存由乘2得到的最小的丑数,同理的i3,i5
为什么i2可以保存×2的最小的丑数呢?因为i2是保存从1开始每一位丑数×2的结果
那么前面的x2的丑数必定比后面的×以2的丑数小
且如果取了当前值为丑数就不能再取了,因此每次需要进行向后＋1,x2最小的值只能来自于下一位了
所有的丑数分为三种类型 2i,3i,5*i 其中 i是数组中的元素，一开始只有1
2*1 3*1 5*1
2*2 3*1 5*1
2*2 3*2 5*1
2*3 3*2 5*1
2*3 3*2 5*2
2*4 3*3 5*2
2*5 3*3 5*2
2*5 3*4 5*2
2*6 3*4 5*3
2*8 3*5 5*3
2*8 3*6 5*4
代码:
public int GetUglyNumber_Solution(int index) {
if(index<=0)return 0;
ArrayList<Integer> list=new ArrayList<Integer>();
list.add(1);
int i2=0,i3=0,i5=0;
while (list.size()<index){
int min = Math.min(Math.min(list.get(i2)*2, list.get(i3)*3), list.get(i5)*5);
list.add(min);
if (min==list.get(i2)*2){
i2++;
}
if (min==list.get(i3)*3){
i3++;
}
if (min==list.get(i5)*5){
i5++;
}
}
return list.get(list.size()-1);
}
提一下为什么这里用if并列三个条件而不是else if,因为这里可能同时出现相同的计算结果,因为这里存在一个丑数公倍数的问题.
