java-64.寻找第N个丑数
public class UglyNumber {/** * 64.查找第N个丑数具体思路可参考 [url] http://zhedahht.blog.163.com/blog/static/2541117420094245366965/[/url] * 题目：我们把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第1500个丑数。 */public static void main(String[] args) {UglyNumber un=new UglyNumber();int n=50;int re=un.findNthUglyNumber2(n);System.out.println(re);}public int findNthUglyNumber1(int n){int count=0;int i=1;while(count<n){if(isUglyNumber(i)){count++;if(count==n){return i;}}i++;}return -1;}public boolean isUglyNumber(int x){while(x%2==0)x/=2;while(x%3==0)x/=3;while(x%5==0)x/=5;return x==1?true:false;}//like finding a SuShu/PrimeNumberpublic int findNthUglyNumber2(int n){int re=-1;int[] a=new int[n];a[0]=1;int p2=0,p3=0,p5=0;int i=1;while(i<n){a[i]=min(a[p2]*2,a[p3]*3,a[p5]*5);while(a[p2]*2<=a[i])p2++;while(a[p3]*3<=a[i])p3++;while(a[p5]*5<=a[i])p5++;i++;}re=a[i-1];return re;}public int min(int a,int b,int c){return (a<b?a:b)<c?(a<b?a:b):c;}}