第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 条评论
登录 后参与评论

相关文章

来自专栏大闲人柴毛毛

剑指 offer代码解析——面试题34丑数

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

2677
来自专栏苍云横渡学习笔记

【慕课-数据结构-C++语言】队列篇

原文地址:https://www.cloudcrossing.xyz/post/30/

40419
来自专栏mathor

数制

845
来自专栏Java开发者杂谈

由归并算法引申出来的其他问题

前言:   上一节刚讲过归并算法是排序算法中比较少见的一种时间复杂度为:θ(nlgn)的算法。而归并算法之所以快的原因在于它用了分治的思想,现实生活中有很多需要...

2726
来自专栏Ryan Miao

Java8-Collect收集Stream

3025
来自专栏magicsoar

全错位排列

全错位排列是由著名数学家欧拉提出的。 最典型的问题是装错信封问题 一个人写了n封不同的信及相应的n个不同的信封,他把这n封信都装错了信封,问都装错信封的装法有多...

17710
来自专栏苍云横渡学习笔记

【慕课-数据结构-C++语言】线性表篇

线性表是n个数据元素的有限序列。可应用与通讯录、一元多项式等等。 ? 顺序表 新建List.h和List.cpp #List.h #ifndef LIST_H ...

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

agc027D - Modulo Matrix(构造 黑白染色)

构造一个$n * n$的矩阵,要求任意相邻的两个数$a,b$,使得$max(a,b) % min(a,b) \not = 0$

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

5929 亲戚

题目描述 Description 若某个家族人员过于庞大,要判断两个是否是亲戚,确实还很不容易,现在给出某个亲戚关系图,求任意给出的两个人是否具有亲戚关系。 规...

2975
来自专栏计算机视觉与深度学习基础

Leetcode 202 Happy Number

Write an algorithm to determine if a number is "happy". A happy number is a nu...

1839

扫码关注云+社区