1,题意:
把只包含质因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含因子7。
习惯上我们把1当做是第一个丑数。
返回第n个丑数.
2,分析: //类似于筛法寻找素数
创建一个数组,里面的数字是排好序的丑数。里面的每一个丑数是前面的丑数乘以2、3或者5得到的。
我们假设数组中已经有若干个丑数,排好序后存在数组中。现在我们来生成下一个丑数,该丑数肯定是前面某一个丑数乘以2、3或者5的结果。
从1开始,每个数分别乘以一次2,3,5,会贡献3个丑数.
贡献后,对应的index2或index3或index5就右移一位.
3,实现代码:
#include <iostream>
using namespace std;
int mymin(int a, int b, int c)
{
int temp = (a < b ? a : b);
return (temp < c ? temp : c);
}
int FindUgly(int n) //返回第n个丑数
{
int* ugly = new int[n];
ugly[0] = 1;
int index2 = 0;
int index3 = 0;
int index5 = 0;
int index = 1;
while (index < n)
{
int val = mymin(ugly[index2]*2, ugly[index3]*3, ugly[index5]*5);
if (val == ugly[index2]*2) //看哪个被选中
++index2;
if (val == ugly[index3]*3)
++index3;
if (val == ugly[index5]*5)
++index5;
ugly[index++] = val;
}
for (int i = 0; i < n; ++i)
cout << ugly[i] << endl;
int result = ugly[n-1];
delete[] ugly;
return result;
}
int main()
{
FindUgly(100);
return 0;
}
分享到:
相关推荐
丑数,又称“好看数”或“优美数”,在数学领域中是指仅包含质因数2、3和5的正整数。这类数的特点是它们可以...通过对这些知识点的理解和应用,我们可以有效地解决寻找一定范围内丑数的问题,例如在边界值1500以内。
理解丑数的概念和C语言实现丑数判断及寻找第n个丑数的算法,有助于提升编程能力和算法思维。在实际应用中,这样的问题可能会出现在数据结构、算法或编程竞赛题目中,熟练掌握丑数相关的知识对于提升编程能力大有裨益...
4. **寻找前n个丑数**: - 在`main`函数中,使用一个循环结构,从1开始逐个判断每个数是否为丑数。 - 用一个计数器`count`记录已找到的丑数个数,直到找到第1500个丑数为止。 - 如果当前数`num`是丑数,就输出它...
本文将深入探讨如何使用最小堆来解决寻找第n个丑数的问题。 首先,我们需要定义丑数的概念。一个数如果仅包含质因子2、3和5,那么它就是丑数。例如,1、2、3、4、5、6、8、9、10和12都是前10个丑数。丑数序列的特点...
《算法设计与分析》课程笔记主要涵盖了算法设计与分析的基础知识,包括算法的重要性和五大特性,以及具体的算法实例,如辗转相除法求最大公约数和寻找丑数的方法。以下是这些知识点的详细说明: 1. **算法的重要性*...
- 寻找丑数。 - **PlusOne** - 数组表示的数字加1。 **5. 链表(LinkedList)** - **RemoveDuplicatesfromSortedList** - 删除排序链表中的重复元素。 - **RemoveDuplicatesfromSortedListII** - 删除排序链表中...
这种方法虽然直观,但效率较低,因为需要对每一个数进行判断,尤其是在寻找较大的丑数时,会浪费大量时间。 ```c int ugly(int number){ while (number % 2 == 0) number /= 2; while (number % 3 == 0) number /...
1.2.2. 下排每个数都是先前上排那十个数在下排出现的次数 ..........................11 1.2.3. 设计包含 min 函数的栈 ...................................................................... 14 1.2.4. 求子...
getNumber--寻找丑数 所谓丑数,就是只含有2、3或5这3个素因子的自然数。如果认为1是一个合法的丑数,那么1就是第一个丑数 leetcode 动态规划 五、最长回文子串 十、正则表达式匹配--动态规划 六十二、不同路径 六十...
根据给定文件的信息,我们可以总结出以下相关的IT知识点: ...综上所述,这段代码通过简洁而高效的逻辑实现了寻找第1500个丑数的功能。通过动态规划的思想和合理的数据结构选择,使得程序运行效率高且易于理解。
初始将1放入堆中,每次从堆中取出最小的丑数x,然后将其与2、3、5相乘得到新的丑数,再将这些新丑数加入堆中。重复此过程,直到堆中的元素个数等于n。这种方法能够确保始终优先处理最小的丑数,从而达到找到第n个丑...
【USACO/humble】此题是关于“丑数”的问题,丑数是指仅包含特定素因子的正整数。题目给出一个素数集合S,求集合S生成的丑数集合中的第N个数。解决这个问题可以采用动态规划的方法,维护一个数组hum,依次计算由S中...
代码中的`It is not ugly number`程序生成并存储了前4000个丑数,然后根据用户输入查询特定位置的丑数。这里使用了动态规划和排序技术,动态规划的核心是避免重复计算,提高效率。在计算过程中,每次生成新的丑数时...
数学问题包括计算阶乘、斐波那契数列、逆波兰表达式的计算、丑数(只包含质因数2、3、5的数)的生成、2的幂次的计算等。处理数学问题时,通常需要对数学规律有深刻理解,如动态规划或递归的思想。 海量数据处理则是...
寻找第n个丑数(动态规划) 寻找唯一重复数字(Floyd判圈法) 链表环路检测(Floyd判圈法) 链表按位求和 超级丑数(动态规划,这次是k个质因子) 戳气球(动态规划,找出状态转移方程最关键) 按字典序去重(利用进栈出栈) 盛...
13. **输出第n个丑数**:丑数是指仅包含质因数2、3、5的数,可以通过动态规划或三个指针维护三个质因数状态来计算。 14. **数字在排序数组中出现的次数**:在有序数组中查找元素的出现次数,可以直接双指针法解决。...
8. 回溯算法:如丑数,二叉搜索树与双向链表等。 9. 字符串操作:包括字符串的排列,表示数值的字符串等。 10. 高级数据结构:例如复杂链表的复制,平衡二叉树,构建乘积数组等。 11. 序列化与反序列化:如序列化...
21. **丑数 II**:丑数是指只包含质因数2、3、5的正整数,可能需要用到动态规划。 22. **根据字符出现频率排序**:字符串处理和排序算法的结合,可以使用计数排序或基数排序。 23. **重构字符串**:字符串操作和...
丑数 009 Easy fizz buzz 013 Easy 字符串查找 014 Easy 二分查找 028 Easy 搜索二维矩阵 031 Medium 数组划分 046 Easy 主元素(贪心) 050 Easy 数组剔除元素后的乘积 055 Medium 比较字符串 056 Medium 两数之和 ...