把只包含质因子2、3和5的数称作丑数(Ugly Number)。
例如6、8都是丑数,但14不是,因为它包含质因子7。 习惯上我们把1当做是第一个丑数。
import java.util.List; import java.util.ArrayList; public class Solution { public int GetUglyNumber_Solution(int index) { if(index <= 0) { return 0; } List<Integer> array = new ArrayList<>(); array.add(1); int t2 = 0; int t3 = 0; int t5 = 0; while(array.size() < index) { int m2 = array.get(t2)*2; int m3 = array.get(t3)*3; int m5 = array.get(t5)*5; int min = Math.min(m2,Math.min(m3,m5)); array.add(min); if(min == m2) { t2++; } if(min == m3) { t3++; } if(min == m5) { t5++; } } return array.get(index -1); } }
求按从小到大的顺序的第N个丑数。