算法:第n个丑数-java
发布日期:2021-06-28 19:59:36
浏览次数:3
分类:技术文章
本文共 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月15日 08时54分24秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
spring boot 与mybatis 整合配置 日志打印
2019-04-29
读 约翰克里斯朵夫
2019-04-29
魔兽世界伯尔瓦公爵黑装备的故事
2019-04-29
mysql 批量插入与单条插入 的效率比较
2019-04-29
读《Redis入门指南》
2019-04-29
读《Redis入门指南》2
2019-04-29
读《JavaScript语言精粹》1
2019-04-29
读《JavaScript语言精粹》2
2019-04-29
读《javaScript 语言精粹》3
2019-04-29
读《java函数式编程》1
2019-04-29
读《java8 函数式编程》2
2019-04-29
贪吃蛇
2019-04-29
今天遇到的Struts2中的几个问题
2019-04-29
使用JQchart 所遇到的兼容性问题
2019-04-29
jqchart 画图表
2019-04-29
批量上传图片前展示
2019-04-29
spring boot中关于redis 保存数据的序列化(数据库中的乱码问题)
2019-04-29
关于在pdf文件中的中文字体显示
2019-04-29
android Preference 的用法
2019-04-29
一个简单的算法关于list
2019-04-29