算法:第n个丑数-java
发布日期:2021-06-28 19:59:36
浏览次数:2
分类:技术文章
本文共 2149 字,大约阅读时间需要 7 分钟。
题目
求第n个丑数
丑数定义
- 1是丑数
- 只包含质因子2,3和5的数称作丑数。如8,6,15
算法思路
一个丑数(除1外)是排在它前边的某个丑数乘以2或者乘以3或者乘以5得到的,那么我们只要在当前得到的丑数集合中找到比当前集合中最大丑数刚刚好大的丑数即可,因为我们要保持有序,才好找到第N个丑数,现在难点是怎么在O(1)时间内就找到一个丑数,使得它乘以2或者乘以3或者乘以5刚刚好大于当前最大丑数呢?
我们设置三个游标:
- 一个表示所指丑数乘以2是下一个可能加入到丑数集合中的丑数
- 一个表示所指丑数乘以3是下一个可能加入到丑数集合中的丑数
- 一个表示所指丑数乘以5是下一个可能加入到丑数集合中的丑数
当我们找到这三个游标,然后分别对应乘以2,3,5后,再比较,拿出最小的那个就是要插入当前丑数集合的丑数。而这三个游标的更新标准是,若当前的游标乘以对应数,大于刚加入的丑数,则不要变,否则就加1.
代码实现
public class UglyNum { private static final int[] times = new int[]{ 2,3,5}; /** 查第n个丑数 丑数定义:只能被2、3、5整除的数。 */ public static int solution(int n) { int[] uglyNumHolder = new int[n]; init(uglyNumHolder); if (n <= 5) { System.out.println(uglyNumHolder[n-1]); return uglyNumHolder[n-1]; } int[] minIndexHolder = new int[]{ 0,0,0};// 0位记录最小2的index,1位记录最小3的index,2位记录最小5的index for (int currentCount = 5;currentCount < n; currentCount++) { for (int i=0; i<3; i++) { while(uglyNumHolder[minIndexHolder[i]] * times[i] <= uglyNumHolder[currentCount - 1] || minIndexHolder[i] >= n) { minIndexHolder[i] = minIndexHolder[i] + 1; } } uglyNumHolder[currentCount] = min(uglyNumHolder[minIndexHolder[0]] * times[0], uglyNumHolder[minIndexHolder[1]] * times[1], uglyNumHolder[minIndexHolder[2]] * times[2]); } System.out.println(uglyNumHolder[n-1]); return uglyNumHolder[n-1]; } private static int min(int a,int b,int c) { int min = a; if (b < min) { min = b; } if (c < min) { min = c; } return min; } public static void main(String[] args) { solution(10); solution(100); solution(1000); solution(1500); } /** 初始化前五个数 */ private static void init(int[] uglyNumHolder) { for (int i=0; i< (uglyNumHolder.length > 5 ? 5 : uglyNumHolder.length); i++) { uglyNumHolder[i] = i+1; } }}
转载地址:https://blog.csdn.net/xxxxssss12/article/details/107670463 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
路过按个爪印,很不错,赞一个!
[***.219.124.196]2024年04月13日 17时07分37秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
C#WinCE 记录日志文件
2019-04-29
C# 读写XML文件,用于配置文件
2019-04-29
PC端到WinCE端文件互相拷贝
2019-04-29
遍历文件夹及子文件夹中的所有文件
2019-04-29
MVC 实现数据导入Excel,并在客户端下载。
2019-04-29
Jquery 实现文本框键盘回车事件
2019-04-29
JQuery 循环读取table中的数据
2019-04-29
JQuery正则表达式
2019-04-29
在bootstrap中实现treeview
2019-04-29
DBGrid 根据表格中数据长度自动调整表格宽度
2019-04-29
delphi中遍历枚举类型的方法
2019-04-29
Delphi 遍历类中的属性
2019-04-29
jsTree发现一个比较好的树形结构
2019-04-29
C#连接MariaDB
2019-04-29
ajax上传大文件
2019-04-29
Android版本和API Level对应关系
2019-04-29
delphi 查找指定目录,指定扩展名的所有文件名
2019-04-29
介绍两款绘图软件免费的
2019-04-29
怎么样使用delphi 中的statusbar控件改变文字颜色
2019-04-29
sql server 2005 自动重新建立索引
2019-04-29