Leetcode 264.丑数II
2024-09-06 15:48:17
丑数II
编写一个程序,找出第 n 个丑数。
丑数就是只包含质因数 2, 3, 5 的正整数。
示例:
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
说明:
- 1 是丑数。
- n 不超过1690。
思路:动态规划思想。后面的丑数一定是由前面的丑数乘以2、3或5得到。所以第n个丑数一定是由前n-1个数中的某3个丑数(分别记为index2、index3、index5)分别乘以2、3或者5得到的数中的最小数,index2,index3,index5有个特点,即分别乘以2、3、5得到的数一定含有比第n-1个丑数大(可利用反证法:否则第n-1个丑数就是它们当中的一个)最小丑数,即第n个丑数由u[index2]*2、u[index3]*3、u[index5]*5中的最小数得出。让它们分别和第n个丑数比较,若和第n个丑数相等,则更新它们的值。注:一次最少更新一个值(如遇到第n个丑数是6时,index2和index3都要更新)。
class Solution {
public static int nthUglyNumber(int n) {
int[] aux=new int[n];
aux[0]=1;
int i2=0;
int i3=0;
int i5=0;
int idx=1;
while(idx<n){
aux[idx]=Math.min(2*aux[i2],Math.min(3*aux[i3],5*aux[i5]));
if(aux[idx]==2*aux[i2]) i2++;
if(aux[idx]==3*aux[i3]) i3++;
if(aux[idx]==5*aux[i5]) i5++;
idx++;
}
return aux[idx-1];
} public static void main(String[] args){
nthUglyNumber(2);
}
}
最新文章
- ListView 的优化
- 为什么.Net要求序列化的类必须有一个无参数的构造函数
- 在Gridview如何进行每行单元格比较
- POJ2135 Farm Tour(最小费用最大流)
- PostgreSQL存储过程(3)-流程控制语句
- HSF服务的开发与使用
- 开发日记:JsonCSharpHelp
- Django组件--分页器(有用)
- 浏览器开发者工具----F12 功能介绍
- 银盒子智慧餐厅硬件尺寸规格&;推荐机型
- js-元素相关
- Python实现代理模式
- Oracle误删除数据的恢复方法(转)
- Jumpserver跳板机的搭建和部署
- Consul集群搭建
- [LOJ 6031]「雅礼集训 2017 Day1」字符串
- 024 关于spark中日志分析案例
- Codeforces Round #213 (Div. 1) B - Free Market 思维+背包 好题
- 常用脚本--SQL Server获取OS日志
- Android技术——在Android中的随意视图中找控件