大家好,又见面了,我是全栈君,今天给大家准备了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開始 } }
版权声明:本文博客原创文章,博客,未经同意,不得转载。
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117395.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...