把仅仅包括质因子2、3和5的数称作丑数（Ugly Number），比如：2,3,4,5,6,8,9,10,12,15,等，习惯上我们把1当做是第一个丑数。

写一个高效算法，返回第n个丑数。

import static java.lang.Math.min;import static java.lang.System.out;public class UglyNumber {	public static void main(String[] args) {		out.println(findKthUglyNumber(1500));	}	/**	 * 寻找第K个丑数	 * 	 * @param k	 * @return	 */	public static int findKthUglyNumber(int k) {		if (k < 0) {			return 1;// 把第一个丑数返回		}		int[] numbers = new int[k];		numbers[0] = 1;		int next = 1;		int ugly2Index = 0;		int ugly3Index = 0;		int ugly5Index = 0;		while (next < k) {			int uglyNum = min(numbers[ugly2Index] * 2,					min(numbers[ugly3Index] * 3, numbers[ugly5Index] * 5));			numbers[next] = uglyNum;			while (numbers[ugly2Index] * 2 <= numbers[next]) {				ugly2Index++;			}			while (numbers[ugly3Index] * 3 <= numbers[next]) {				ugly3Index++;			}			while (numbers[ugly5Index] * 5 <= numbers[next]) {				ugly5Index++;			}			next++;		}		return numbers[k - 1];// 从0開始	}}

版权声明：本文博客原创文章，博客，未经同意，不得转载。