当前位置:网站首页>首先看K一个难看的数字
首先看K一个难看的数字
2022-07-06 10:19:00 【全栈程序员站长】
大家好,又见面了,我是全栈君。
把仅仅包括质因子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.cn/117395.html原文链接:https://javaforall.cn
边栏推荐
- 队列的实现
- DNS hijacking
- UDP协议:因性善而简单,难免碰到“城会玩”
- 简单易用的PDF转SVG程序
- 2022 Summer Project Training (II)
- Grafana 9.0 正式发布!堪称最强!
- Declval (example of return value of guidance function)
- [swoole series 2.1] run the swoole first
- Pourquoi Li shufu a - t - il construit son téléphone portable?
- MSF horizontal MSF port forwarding + routing table +socks5+proxychains
猜你喜欢
Pourquoi Li shufu a - t - il construit son téléphone portable?
模板于泛型编程之declval
STM32 key state machine 2 - state simplification and long press function addition
阿里云国际版ECS云服务器无法登录宝塔面板控制台
面向程序员的精品开源字体
Getting started with pytest ----- test case pre post, firmware
UDP protocol: simple because of good nature, it is inevitable to encounter "city can play"
递归的方式
Windows连接Linux上安装的Redis
The easycvr authorization expiration page cannot be logged in. How to solve it?
随机推荐
Jerry's watch reading setting status [chapter]
TOP命令详解
二分(整数二分、实数二分)
SAP Fiori 应用索引大全工具和 SAP Fiori Tools 的使用介绍
传输层 拥塞控制-慢开始和拥塞避免 快重传 快恢复
微信为什么使用 SQLite 保存聊天记录?
1700C - Helping the Nature
2022暑期项目实训(一)
ASEMI整流桥DB207的导通时间与参数选择
J'aimerais dire quelques mots de plus sur ce problème de communication...
關於這次通信故障,我想多說幾句…
Heavy! Ant open source trusted privacy computing framework "argot", flexible assembly of mainstream technologies, developer friendly layered design
Maixll-Dock 摄像头使用
Dichotomy (integer dichotomy, real dichotomy)
Insert dial file of Jerry's watch [chapter]
Stealing others' vulnerability reports and selling them into sidelines, and the vulnerability reward platform gives rise to "insiders"
Five data structures of redis
Jielizhi obtains the customized background information corresponding to the specified dial [chapter]
QT中Model-View-Delegate委托代理机制用法介绍
Getting started with pytest ----- test case rules