Leetcode 264. Ugly Number II-输出前n个丑数（从小到大）

最新推荐文章于 2024-05-20 21:13:17 发布

二十六画生的博客

最新推荐文章于 2024-05-20 21:13:17 发布

阅读量623

点赞数

分类专栏：笔试面经 LeetCode 剑指Offer 后端/大数据文章标签： Leetcode 264 Ugly Number II 前n个丑数

本文链接：https://blog.csdn.net/u010002184/article/details/85868646

版权

笔试面经 LeetCode 剑指Offer 后端/大数据专栏收录该内容

226 篇文章 ¥9.90 ¥99.00

订阅专栏

超级会员免费看

这篇博客介绍了如何解决LeetCode第264题，即找出第n个丑数。丑数是指仅包含质因数2、3和5的正整数。文中提供了一个时间复杂度为O(n)的Java解决方案，通过不断比较并更新乘以2、3和5的较小数值来找到下一个丑数，确保结果不超过1690。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.

Example:

Input: n = 10
Output: 12
Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note:

1 is typically treated as an ugly number.
n does not exceed 1690.

方法1：

public class Leetcode_264_UglyNumberII {

    public static void main(String[] args) {
        Leetcode_264_UglyNumberII leetcode_264_uglyNumb

了解本专栏

订阅专栏解锁全文

超级会员免费看

确定要放弃本次机会？

福利倒计时

: :

立减 ¥

普通VIP年卡可用

立即使用

二十六画生的博客

关注关注

0
点赞
踩
0

收藏

觉得还不错? 一键收藏
2
评论
分享

复制链接

分享到 QQ

分享到新浪微博

扫一扫
打赏
打赏
打赏举报

举报

专栏目录

订阅专栏

C++版 - 剑指offer 面试题34：寻找丑数(Leetcode 263.Ugly number)解题报告

极客学长Bravo | 突破信息差 | 副业生财有术

05-07

3466

剑指offer 面试题34：寻找丑数题目：把只包含因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数，但14不是，因为它包含因子7。习惯上我们把1当做是第一个丑数。请按从小到大的顺序的第N个丑数。(据说google曾经采用过这道题。) 提交网址： http://www.nowcoder.com/practice/6aa9e04fc3794f68acf87

关于丑数(只包含质因子 2、3 和 5 的数称作丑数,求按从小到大的顺序的第 n 个丑数。)

Oblak_ZY的博客

05-19

505

丑数我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。示例: 输入: n = 10 输出: 12 解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。这道题真的必须要好好研究一下了,我们得到的丑数一定是之前的丑数的 2、3 、5倍,并且当前位置要得到丑数只是取其中最小的那个. 因此我们定义三个指针p2、p3、p5分别代表当前2、3 、5这些系数所叠加的丑数的索引位置index,也就是说当前该系数所得

2 条评论您还未登录，请先登录后发表或查看评论

LeetCode 264. Ugly Number II（丑数II）

马一凡的博客

02-21

293

题目：思路1（超时）：这是最初的思路，因为丑数可以被2和3还有5整除直到为1，所以可以从1开始逐个去找并累加，分别用判断能否被2整除，如果可以就除2，再次重复这样的步骤，直到不能被2整除，再分别拿3和5做同样的事情。最终剩下的是1就说明这是一个丑数，用这样的方式去找第n个就可以了。这种方式很好理解，但是容易超时。因为它做了一些重复的事情，比如每个数都要追溯到不能被2和3还有5整除。思路2（...

求前n个丑数的方法

蒸发杰作的博客

09-28

434

例如寻找2，3，5相乘得到的数字。即进行状态拆分结果为，原始状态 #抽数列表有序 uglys=[2] #维护的三个位置pos poss=[0,0,0] #item items=[2,3,5] while True: if len(uglys)==10: break # can_choose=[uglys[poss[i]]*items[i] for i in...

leetcode 264: Ugly Number II

西施豆腐渣

08-23

6088

Ugly Number II Total Accepted: 2920 Total Submissions: 15174 Write a program to find the n-th ugly number. Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For

leetcode笔记：Ugly Number II

liyuefeilong的专栏

01-10

2350

从1开始的丑数为：1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, … 该题的大意是，输入一个正整数n，返回第n个丑数。

LeetCode OJ 之 Ugly Number II （丑数-二）

灯火阑珊处

08-19

1848

题目： Write a program to find the n-th ugly number. Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of t

264. Ugly Number II （python+cpp）

qq_37821701的博客

08-25

422

Leetcode 264. Ugly Number II题目解法1：brutal force(TLE)改进的思路：解法2：heap解法3：三指针法题目解法1：brutal force(TLE) 一个个判断每个数字是否ugly class Solution: def nthUglyNumber(self, n: int) -> int: def isugly(num): if num == 0: return Fals

[leetcode]第 n个丑数

最新发布

xiaocong1990的博客

05-20

284

我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。输入: n = 10。n 不超过1690。

[LeetCode] Ugly Number II

g9746463的博客

08-31

203

Write a program to find the n-th ugly number. Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first

LeetCode 264 丑数

weixin_43175029的博客

06-30

124

我的解法是，一个数整除2、3、5后得到的数还是丑数的话，那么这个数一定是丑数，但是果不其然的超时了。。。 class Solution { //超时 public: int f[1000000]; //表示以i为下标的数是否是丑数 int d[3]={2,3,5}; int nthUglyNumber(int n) { if(n==1) ...

leetcode264丑数

zsjwish的博客

04-20

593

lee264 丑数题目描述：丑数是因子只包含2,3,5的数字，1也算是第一个丑数，求第n大的丑数是什么。输入：int n 输出：第n大的丑数思路：首先1是丑数，将1放入结果数组中。设定一个index2，index3,index5初始化都为0，代表各自的factor已经遍历了结果数组的位置，因为只要结果数组中前一个是丑数，那么它乘上2,3,5肯定也是丑数。然

Leetcode Ugly Number II

每天都要有进步

02-05

278

找到第N个丑数

如风

06-27

8750

什么是丑数呢？丑数就是只包含因子2，3，5的数称作是丑数，在这里这种定义我是比较模糊的，所以上网查找了更加浅显的定义，丑数就是另一个丑数乘以2，3，5以后的结果（1除外，通常认为1是最小的丑数）。通常，最简单的方法肯定是遍历数组，然后确定每一个数是否是丑数，这种方法是最简单并且直观的。 bool IsUgly(int num) { while (num % 2 == 0)

LeetCode 264. 丑数 II

Logan

05-07

129

编写一个程序，找出第n个丑数。丑数就是只包含质因数2, 3, 5的正整数。示例: 输入: n = 10 输出: 12 解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。说明: 1是丑数。 n不超过1690。三指针法。保证丑数是有序的自小到大排列的，每个丑数都能被枚举到。 class Solution { publ...

leetcode第264题丑数|| （动态规划）

云飞扬的博客

10-10

403

编写一个程序，找出第 n 个丑数。丑数就是只包含质因数 2, 3, 5 的正整数。示例: 输入: n = 10 输出: 12 解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。说明: 1 是丑数。 n 不超过1690。 /* 并不用每次都尝试所有组合，我们需要过滤掉不可能的组合已知2，3，5与已有丑数相乘时，数值增长速度是不一样的我们每次从三组新丑...

leetcode#第n个丑数

u011089927的专栏

07-19

244

class Solution { public: int nthUglyNumber(int n) { if(n<=0) return 0; vector<int> res; res.push_back(1); int id2=0; int id3=0; int id5=0; for(int i=1;i<n;i++) { int m.