大家好，又见面了，我是全栈君，今天给大家准备了Idea注册码。
把仅仅包括质因子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開始
}
}
版权声明：本文博客原创文章，博客，未经同意，不得转载。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/117395.html原文链接：https://javaforall.net
