丑数II

题意

设计一个算法,找出只含素因子235 的第 n 大的数。

符合条件的数如:1, 2, 3, 4, 5, 6, 8, 9, 10, 12...

注意事项:我们可以认为 1 也是一个丑数

样例

如果n = 9, 返回 10

思路

其实改题的题意就是在所有 丑数 列表中,找到第 n 个丑数。

最简单的做法是从 1 开始,判断每一个数是否是一个丑数,是的话则加到丑数列表中,直到丑数列表的大小等于 n,但是这种方法效率较低,我们可以根据规律而尝试只创造出有效的丑数。

1*2=2 2*2=4  3*2=6  4*2=8  5*2=10 ...
1*3=3 2*3=6  3*3=9  4*3=12 5*3=15 ...
1*5=5 2*5=10 3*5=15 4*5=20 5*5=25 ...

观察规律可得,丑数是取已有的丑数乘以 2 或 3 或 5 得到的,那么我们可以先将特殊的丑数 1 放进丑数列表中。

因为已存在的丑数肯定在列表中是按照顺序存放的,所以对于乘以 2 而言,肯定存在一个丑数 p2,在它之前的每一个丑数乘以 2 都是当前列表中最后一个丑数的,通用,在它之后的每一个丑数乘以 2 的结果都是大于当前列表中最后一个丑数的,我们只需要记住 p2 的这个位置,同样存在的还有 p3 和 p5,记住这 3 个数的位置,就可以一些避免不必要的比较。

我们只需要取出 p2, p3, p5 位置的那个数,分别乘以 2, 3, 5 将结果最小的存入到丑数列表中即可。直到丑数列表的个数达到 n。

代码实现

public class Solution {
    /*
     * @param n: An integer
     * @return: the nth prime number as description.
     */
    public int nthUglyNumber(int n) {
        if (n == 1) {
            return 1;
        }
        List<Integer> uglys = new ArrayList<Integer>();
        uglys.add(1);
        
        int p2 = 0, p3 = 0, p5 = 0;
        for (int i = 1; i < n; i++) {
            int lastUgly = uglys.get(i - 1);
            while (uglys.get(p2) * 2 <= lastUgly) p2++;
            while (uglys.get(p3) * 3 <= lastUgly) p3++;
            while (uglys.get(p5) * 5 <= lastUgly) p5++;
            
            uglys.add(Math.min(
                Math.min(uglys.get(p2) * 2, uglys.get(p3) * 3),
                uglys.get(p5) * 5)
                );
        }
        
        return uglys.get(n -1);
    }
};

原题地址

LintCode:丑数II

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 超级丑数

    一份执着✘
  • Python 函数

    一份执着✘
  • Spring 动态注入依赖设计

    最近在开发一个在线网盘的功能, 支持多个存储策略. 启动时, 读取数据库, 获取当前启用的存储类型, 然后项目启动后, 还可以动态切换存储类型.

    一份执着✘
  • 剑指 offer代码解析——面试题34丑数

    本题详细解析均在代码注释中: /** * 题目:我们把只包含因子2、3、5的数称为丑数。求从小到大顺序第1500个丑数。习惯上把1称为第一个丑数。 * @a...

    大闲人柴毛毛
  • AngularJs之路由配置(二)

    我们使用 <a [routerLink]="['/prouct',1]" >商品详情</a>

    黄林晴
  • 2019 开发者调查报告:Java 最流行,Go 最有前途

    知名软件开发公司 JetBrains 近日发布了名为「2019 开发人员生态系统现状」的调查报告。

    xcbeyond
  • 人物|十年轮回

    TEG云端专业号
  • (2)SQL语句实现表的横向聚合

    经过sql查询后输出的结果集为:(字段后面增加聚合[最大值] [最小值] [>=5的值个数])

    跟着阿笨一起玩NET
  • python数据挖掘:能不能找出吃货最佳住宿点?

    这次我爬出了哈尔滨市TOP285家好吃的店,包括烧烤的TOP,饺子的TOP,酱骨的TOP等等等等,在地图上显示,规划热点,再用聚类算法计算下能不能找出吃货最佳的...

    机器学习AI算法工程
  • 你最爱的编辑器是哪一款?快来认领对应的性格特质

    市面上有着各种各样的文档编辑器,不同的人选择了不同的编辑器。其实,你的选择在一定程度上反映了你的个性特征。今天,我们就来盘点一下不同编辑器对应的特质吧。

    HuangWeiAI

扫码关注云+社区

领取腾讯云代金券