`
caoruntao
  • 浏览: 480988 次
  • 性别: Icon_minigender_1
  • 来自: 西安
社区版块
存档分类
最新评论

寻找丑数

 
阅读更多

【转】http://zhedahht.blog.163.com/blog/static/2541117420094245366965/

 

题目:我们把只包含因子235的数称作丑数(Ugly Number)。例如68都是丑数,但14不是,因为它包含因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第1500个丑数。

 

 

分析:这是一道在网络上广为流传的面试题,据说google曾经采用过这道题。

所谓一个数m是另一个数n的因子,是指n能被m整除,也就是n % m == 0。根据丑数的定义,丑数只能被235整除。也就是说如果一个数如果它能被2整除,我们把它连续除以2;如果能被3整除,就连续除以3;如果能被5整除,就除以连续5。如果最后我们得到的是1,那么这个数就是丑数,否则不是。

基于前面的分析,我们可以写出如下的函数来判断一个数是不是丑数:

bool IsUgly(int number)

{

    while(number % 2 == 0)

        number /= 2;

    while(number % 3 == 0)

        number /= 3;

    while(number % 5 == 0)

        number /= 5;

 

    return (number == 1) ? true : false;

}

接下来,我们只需要按顺序判断每一个整数是不是丑数,即:

int GetUglyNumber_Solution1(int index)

{

    if(index <= 0)

        return 0;

 

    int number = 0;

    int uglyFound = 0;

    while(uglyFound < index)

    {

        ++number;

 

        if(IsUgly(number))

        {

            ++uglyFound;

        }

    }

 

    return number;

}

我们只需要在函数GetUglyNumber_Solution1中传入参数1500,就能得到第1500个丑数。该算法非常直观,代码也非常简洁,但最大的问题我们每个整数都需要计算。即使一个数字不是丑数,我们还是需要对它做求余数和除法操作。因此该算法的时间效率不是很高。

接下来我们换一种思路来分析这个问题,试图只计算丑数,而不在非丑数的整数上花费时间。根据丑数的定义,丑数应该是另一个丑数乘以23或者5的结果(1除外)。因此我们可以创建一个数组,里面的数字是排好序的丑数。里面的每一个丑数是前面的丑数乘以23或者5得到的。

这种思路的关键在于怎样确保数组里面的丑数是排好序的。我们假设数组中已经有若干个丑数,排好序后存在数组中。我们把现有的最大丑数记做M。现在我们来生成下一个丑数,该丑数肯定是前面某一个丑数乘以23或者5的结果。我们首先考虑把已有的每个丑数乘以2。在乘以2的时候,能得到若干个结果小于或等于M的。由于我们是按照顺序生成的,小于或者等于M肯定已经在数组中了,我们不需再次考虑;我们还会得到若干个大于M的结果,但我们只需要第一个大于M的结果,因为我们希望丑数是按从小到大顺序生成的,其他更大的结果我们以后再说。我们把得到的第一个乘以2后大于M的结果,记为M2。同样我们把已有的每一个丑数乘以35,能得到第一个大于M的结果M3M5。那么下一个丑数应该是M2M3M5三个数的最小者。

前面我们分析的时候,提到把已有的每个丑数分别都乘以235,事实上是不需要的,因为已有的丑数是按顺序存在数组中的。对乘以2而言,肯定存在某一个丑数T2,排在它之前的每一个丑数乘以2得到的结果都会小于已有最大的丑数,在它之后的每一个丑数乘以2得到的结果都会太大。我们只需要记下这个丑数的位置,同时每次生成新的丑数的时候,去更新这个T2。对乘以35而言,存在着同样的T3T5

有了这些分析,我们不难写出如下的代码:

int GetUglyNumber_Solution2(int index)

{

    if(index <= 0)

        return 0;

 

    int *pUglyNumbers = new int[index];

    pUglyNumbers[0] = 1;

    int nextUglyIndex = 1;

 

    int *pMultiply2 = pUglyNumbers;

    int *pMultiply3 = pUglyNumbers;

    int *pMultiply5 = pUglyNumbers;

 

    while(nextUglyIndex < index)

    {

        int min = Min(*pMultiply2 * 2, *pMultiply3 * 3, *pMultiply5 * 5);

        pUglyNumbers[nextUglyIndex] = min;

 

        while(*pMultiply2 * 2 <= pUglyNumbers[nextUglyIndex])

            ++pMultiply2;

        while(*pMultiply3 * 3 <= pUglyNumbers[nextUglyIndex])

            ++pMultiply3;

        while(*pMultiply5 * 5 <= pUglyNumbers[nextUglyIndex])

            ++pMultiply5;

 

        ++nextUglyIndex;

    }

 

    int ugly = pUglyNumbers[nextUglyIndex - 1];

    delete[] pUglyNumbers;

    return ugly;

}

 

int Min(int number1, int number2, int number3)

{

    int min = (number1 < number2) ? number1 : number2;

    min = (min < number3) ? min : number3;

 

    return min;

}

和第一种思路相比,这种算法不需要在非丑数的整数上做任何计算,因此时间复杂度要低很多。感兴趣的读者可以分别统计两个函数GetUglyNumber_Solution1(1500)GetUglyNumber_Solution2(1500)的运行时间。当然我们也要指出,第二种算法由于要保存已经生成的丑数,因此需要一个数组,从而需要额外的内存。第一种算法是没有这样的内存开销的。

分享到:
评论

相关推荐

    经典数据算术----丑数

    丑数,又称“好看数”或“优美数”,在数学领域中是指仅包含质因数2、3和5的正整数。这类数的特点是它们可以...通过对这些知识点的理解和应用,我们可以有效地解决寻找一定范围内丑数的问题,例如在边界值1500以内。

    丑数实验报告C语言.docx

    4. **寻找前n个丑数**: - 在`main`函数中,使用一个循环结构,从1开始逐个判断每个数是否为丑数。 - 用一个计数器`count`记录已找到的丑数个数,直到找到第1500个丑数为止。 - 如果当前数`num`是丑数,就输出它...

    丑数(最小堆)1

    本文将深入探讨如何使用最小堆来解决寻找第n个丑数的问题。 首先,我们需要定义丑数的概念。一个数如果仅包含质因子2、3和5,那么它就是丑数。例如,1、2、3、4、5、6、8、9、10和12都是前10个丑数。丑数序列的特点...

    《算法设计与分析》课程笔记(无水印文字可选中版) by 浅若清风cyf

    《算法设计与分析》课程笔记主要涵盖了算法设计与分析的基础知识,包括算法的重要性和五大特性,以及具体的算法实例,如辗转相除法求最大公约数和寻找丑数的方法。以下是这些知识点的详细说明: 1. **算法的重要性*...

    数据结构与算法题解

    - 寻找丑数。 - **PlusOne** - 数组表示的数字加1。 **5. 链表(LinkedList)** - **RemoveDuplicatesfromSortedList** - 删除排序链表中的重复元素。 - **RemoveDuplicatesfromSortedListII** - 删除排序链表中...

    丑数c语言,两种解法,详细过程

    这种方法虽然直观,但效率较低,因为需要对每一个数进行判断,尤其是在寻找较大的丑数时,会浪费大量时间。 ```c int ugly(int number){ while (number % 2 == 0) number /= 2; while (number % 3 == 0) number /...

    世界500强面试题.pdf

    1.2.2. 下排每个数都是先前上排那十个数在下排出现的次数 ..........................11 1.2.3. 设计包含 min 函数的栈 ...................................................................... 14 1.2.4. 求子...

    leetcode跳跃-learnning_algorithm:算法学习

    getNumber--寻找丑数 所谓丑数,就是只含有2、3或5这3个素因子的自然数。如果认为1是一个合法的丑数,那么1就是第一个丑数 leetcode 动态规划 五、最长回文子串 十、正则表达式匹配--动态规划 六十二、不同路径 六十...

    求第1500个只有2,3,5因子的数

    根据给定文件的信息,我们可以总结出以下相关的IT知识点: ...综上所述,这段代码通过简洁而高效的逻辑实现了寻找第1500个丑数的功能。通过动态规划的思想和合理的数据结构选择,使得程序运行效率高且易于理解。

    华南农业大学计算智能期末复习.docx

    代码中的`It is not ugly number`程序生成并存储了前4000个丑数,然后根据用户输入查询特定位置的丑数。这里使用了动态规划和排序技术,动态规划的核心是避免重复计算,提高效率。在计算过程中,每次生成新的丑数时...

    算法合集解析_275.pdf

    数学问题包括计算阶乘、斐波那契数列、逆波兰表达式的计算、丑数(只包含质因数2、3、5的数)的生成、2的幂次的计算等。处理数学问题时,通常需要对数学规律有深刻理解,如动态规划或递归的思想。 海量数据处理则是...

    戳气球leetcode-leetcode-solution:实践

    寻找第n个丑数(动态规划) 寻找唯一重复数字(Floyd判圈法) 链表环路检测(Floyd判圈法) 链表按位求和 超级丑数(动态规划,这次是k个质因子) 戳气球(动态规划,找出状态转移方程最关键) 按字典序去重(利用进栈出栈) 盛...

    《算法最优解(第一版)》剑指Offer题解校招求职刷题必备.docx

    13. **输出第n个丑数**:丑数是指仅包含质因数2、3、5的数,可以通过动态规划或三个指针维护三个质因数状态来计算。 14. **数字在排序数组中出现的次数**:在有序数组中查找元素的出现次数,可以直接双指针法解决。...

    剑指Offer---Java版代码

    8. 回溯算法:如丑数,二叉搜索树与双向链表等。 9. 字符串操作:包括字符串的排列,表示数值的字符串等。 10. 高级数据结构:例如复杂链表的复制,平衡二叉树,构建乘积数组等。 11. 序列化与反序列化:如序列化...

    前端大厂最新面试题-heap.docx

    21. **丑数 II**:丑数是指只包含质因数2、3、5的正整数,可能需要用到动态规划。 22. **根据字符出现频率排序**:字符串处理和排序算法的结合,可以使用计数排序或基数排序。 23. **重构字符串**:字符串操作和...

    leetcode跳跃-LeetCode:力码

    丑数 009 Easy fizz buzz 013 Easy 字符串查找 014 Easy 二分查找 028 Easy 搜索二维矩阵 031 Medium 数组划分 046 Easy 主元素(贪心) 050 Easy 数组剔除元素后的乘积 055 Medium 比较字符串 056 Medium 两数之和 ...

    刀疤鸭之数据结构面试题

    文件中还列举了其他诸多数据结构面试题目,如链表操作、栈的使用、整数矩阵的运算、递归实现二叉树遍历、字符串匹配、动态规划问题、单例模式的设计、丑数的寻找、数组和链表的操作等。 这些问题不仅能够考查应聘...

    剑指offer(牛客网)

    31. 丑数:只包含质因数2、3和5的正整数。 32. 第一个只出现一次的字符:找出字符串中第一个只出现一次的字符。 33. 数组中的逆序对:计算数组中的逆序对个数。 34. 整数中1出现的次数(从1到n整数中1出现的次数...

    (1912制作)诺西笔试题面试题

    - 解析:通过动态规划方法寻找第1500个丑数。首先构建一个数组保存已找到的丑数,然后分别用2、3、5去乘以当前已知最小的丑数,更新下一个丑数,直到找到第1500个为止。 - 示例实现: ```c #include unsigned ...

Global site tag (gtag.js) - Google Analytics