丑数__牛客网

LaN666

发表于 2021-06-20 20:10:24

精华题解 33、丑数解题思路：我们先看到题目，把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。习惯上我们把1当做是第一个丑数。有了上面的定义我们就可以知道，丑数的形式就是2x3y5z所以我们可以定义一个数组res，存储第n个丑数。因为展开全文

GhostLX

发表于 2021-06-21 17:57:53

精华题解题目陈述描述：把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。算法一：质因数分解（暴力）算法实现一个很朴素的做法从每次+1，一直枚举，直到找到地N个丑数为展开全文

江南好___

发表于 2021-06-23 14:25:34

精华题解描述题目描述把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。示例输入：7 返回值：8引言对于这种看似复杂的题目，不妨先通过简单的例子计算，进而推到出完整过程展开全文

不会做题的小菜鸡

发表于 2021-07-15 14:31:26

精华题解思路根据题中定义，我们了解到丑数都是可以拆分为 2^x*3^y*5^z 的数字，因此思路集中在解决质因数的分解问题上，如何巧妙地利用质因数会衍生出不同的思路暴力解法（超时）：直接判断每一个自然数是否是符合丑数的质因数分解规律最小堆解法：维护一个丑数最小堆，每次从堆顶取出当前最小值i，并再将2 展开全文

牛客题解官

发表于 2022-04-25 19:10:21

精华题解题目的主要信息：把只包含质因子2、3和5的数称作丑数求按从小到大的顺序的第n个丑数 1视作第一个丑数方法一：最小堆（推荐使用）知识点1：优先队列优先队列即PriorityQueue，是一种内置的机遇堆排序的容器，分为大顶堆与小顶堆，大顶堆的堆顶为最大元素，其余更小的元素在堆下方，小顶堆展开全文

认认真真coding

发表于 2021-07-17 14:41:03

精华题解题目描述把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。方法一：暴力求解求解思路对于求解丑数，因为题目要求丑数的质因子只能为2，3，5.根据整数可以唯一被质数表示可展开全文

2019113913

发表于 2021-07-18 22:28:41

精华题解题意思路：把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。方法一：数学枚举丑数是只包含质因子2、3和5的数，可以从小到大枚举满足条件的数先将满足条件的最小的展开全文

郭家兴0624

发表于 2019-08-11 11:58:13

题目描述把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。思路：我们可以维护三个list，分别是乘2得到的丑数，乘3得到的丑数，乘5得到的丑数，但这样复杂度较高，而且展开全文

年少挽剑世无双·

发表于 2020-03-19 21:41:51

题目描述把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。解答：刚看到这个题目，想的是丑数排序有什么样的规律，但是发现前一个丑数和后一个丑数似乎没有任何规律。看了别人展开全文

FYZ~

发表于 2019-07-30 01:36:11

题目：把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。思路：一个丑数成以2/3/5，得到的还是一个丑数；有3个对列pos2/pos3/pos5，每次都取最小的数，放展开全文

牛客524296088号

发表于 2020-06-25 20:47:41

丑数第n个丑数肯定是第i个丑数乘以2,3或5得来的，1<=i<=n-1 考虑从前往后的动态规划求解丑数，假如已知前n-1个丑数，求解第n个丑数，那么三个指针p2,p3,p5,分别指向三个分别乘以2,3,5正好大于第n-1个丑数的丑数，求得三个乘积的最小值即为第n个丑数。求出第n个丑展开全文

xiongqiangcs

发表于 2020-04-29 00:43:26

class Solution { public: int GetUglyNumber_Solution(int index) { if (index <= 0) return 0; vector<int> ugly(index); 展开全文

超级码力233

发表于 2020-11-26 19:22:49

丑数题目链接 Solution 丑数是任意个2,3,5相乘得到的。每个丑数都可以乘以一个2,3,5得到一个新的丑数。根绝这个思想，我们可以递推出所有的丑数。首先定义一个数组存储所有的丑数，并从头开始扫描所有丑数，每个丑数都乘以2,3,5，得到新的丑数。所以设三个指针分别表示接拿下来轮到那个数乘2, 展开全文

翟邦杰

发表于 2020-02-28 03:11:34

思路：我和想的方法和主流方法不一样，暴力打表。附上代码，难点在于确定指数范围。题目描述把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。 cla 展开全文

waigo

发表于 2021-09-20 11:15:23

import java.util.*; public class Solution { /*public int GetUglyNumber_Solution(int index) { //很明显，丑数除了2,3,5之外其他丑数肯定都是由丑数乘来的，不是丑数的数乘啥都不会变成展开全文

宫水三叶的刷题日记

发表于 2021-07-26 16:14:09

基本思路根据丑数的定义，我们有如下结论：是最小的丑数。对于任意一个丑数，其与任意的质因数（、、）相乘，结果（、、）仍为丑数。优先队列（小根堆）解法有了基本的分析思路，一个简单的解法是使用优先队列：起始先将最小丑数放入队列每次从队列取出最小值，然后将所对应的丑数、展开全文

ccจุ๊บ

发表于 2020-02-13 01:08:00

丑数 = 已有的丑数 * (2,3,5) 得到三个新的丑数，但是新的丑数位置不一定正确，切可能会有重复所以我们每次只新增一个最小值，然后用三个指针记录当前2，3，5质因子形成的最大丑数位置，这样的话就会形成递增的丑数队列，而且遍历的次数也很容易就知道，即n-1,因为1是第一个丑数，n-1次遍历后，展开全文

丑数

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题