第n个丑数

【题目描述】 把只包含因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。 【思路】 首先想到的是肯定是暴力法,从1,2,3,…循环一直找到给定的第n个丑数,但是这种做法我记得在LeetCode是TLE的。那么有没有更elegant的方法呢?以下思路来自《剑指offer》第34题。 既然一个个循环不可行,那么就生成第n个丑数呗。 由于丑数只包含因子2,3,5,那么我们一个丑数只乘2,3,5的话也可以得到丑数。由于1是一个丑数,那么分别乘上2,3,5可以得2,3,5。显然,它们是丑数。但是注意4也是一个丑数,它可以由2 x 2得到。所以丑数可以再乘以2,3,5得到下一个丑数,唯一要保证的是应该从小到大得到下一个丑数。所以要分别保留2,3,5的上一个丑数指针,下一个丑数则是三个指针所指的数值分别乘以对应的因子中的最小值。

public class Solution {
    public int GetUglyNumber_Solution(int index) {
       if(index==0) return 0;//注意0的情况,没有加这一行牛客网上显示通过0%
       int count=1;
        int index_2=0,index_3=0,index_5=0;//三个因子的指针
        int number=1;
        int[] uglyNumber=new int[index];//用于保存前index个丑数
        uglyNumber[0]=1;
        while(count<index){
            int tmpnumber_2=uglyNumber[index_2]*2;
            int tmpnumber_3=uglyNumber[index_3]*3;
            int tmpnumber_5=uglyNumber[index_5]*5;
            number=Math.min(tmpnumber_2,Math.min(tmpnumber_3, tmpnumber_5));//最小的数作为下一个丑数
            uglyNumber[count]=number;
            while(uglyNumber[index_2]*2<=uglyNumber[count])
                index_2++;
            while(uglyNumber[index_3]*3<=uglyNumber[count])
                index_3++;
            while(uglyNumber[index_5]*5<=uglyNumber[count])
                index_5++;
            count++;
        }
        return number;
    }
}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏tkokof 的技术,小趣及杂念

Sweet Snippet系列 之 随机选择

  平日工作学习时总会遇到一些令人欣喜的代码段子(Snippet),虽然都很短小,但是其间所含的道理都颇有意味,遂而觉得应该不时的将她们记下,一来算作复习整理,...

1032
来自专栏赵俊的Java专栏

超级丑数

1223
来自专栏数据结构与算法

BZOJ4514: [Sdoi2016]数字配对(费用流)

Description 有 n 种数字,第 i 种数字是 ai、有 bi 个,权值是 ci。 若两个数字 ai、aj 满足,ai 是 aj 的倍数,且 ai/a...

3427
来自专栏成长道路

OneHotEncoder介绍单属性多属性scala实现

       因为项目的需要,将数据库中表的属性向量化,然后进行机器学习,所以去spark官网学习了一下OneHotEncoder,官网的相关介绍比较少,主要是...

2640
来自专栏数据结构与算法

2017.7.21夏令营清北学堂解题报告

预计分数: 60+30+0=90=划水 实际分数: 90+30+20=140=rank5=雷蛇鼠标 一句话总结:今天该买彩票! T1: 题目描述 从前有一个?...

2716
来自专栏小樱的经验随笔

浅谈切比雪夫多项式推导及其实现模版归类

切比雪夫多项式 概述: 切比雪夫多项式是与棣美弗定理有关,以递归方式定义的一系列正交多项式序列。 通常,第一类切比雪夫多项式以符号Tn表示, 第二类切比雪夫多项...

4075
来自专栏算法修养

浙江工业大学校赛 XiaoWei的战斗力

XiaoWei的战斗力 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768...

3258
来自专栏数值分析与有限元编程

可视化 | 平面四节点等参单元后处理

等参数单元得出的结点应力是高斯积分点应力,需要经过外推才能得到结点应力。但是,单元间的应力分布并不连续,还需经过磨平处理。以下是外推和磨平的代码: ? ? 一个...

2833
来自专栏深度学习之tensorflow实战篇

稀疏矩阵压缩sparse.csr_matrix函数与sparse.csc_matric详解

概述 在用python进行科学运算时,常常需要把一个稀疏的np.array压缩,这时候就用到scipy库中的sparse.csr_matrix(csr:Comp...

3675
来自专栏小樱的经验随笔

2017广东工业大学程序设计竞赛决赛 题解&源码(A,数学解方程,B,贪心博弈,C,递归,D,水,E,贪心,面试题,F,贪心,枚举,LCA,G,dp,记忆化搜索,H,思维题)

心得: 这比赛真的是不要不要的,pending了一下午,也不知道对错,直接做过去就是了,也没有管太多! Problem A: 两只老虎 Description ...

3036

扫码关注云+社区