剑指Offer面试题:29.丑数

一、题目:丑数

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

二、两种解决方案

2.1 一一遍历法:时间效率低下

  使用遍历法求第k个丑数,从1开始遍历,如果是丑数则count++,直到count=k为止。那么如何判断丑数呢?根据丑数的定义,丑数只有2,3,5这三个因子,那么我们就拿数字除以这三个因子。具体算法如下:

Step1.如果一个数能够被2整除,那么让他继续除以2; Step2.如果一个数能够被3整除,那么让他继续除以3; Step3.如果一个数能够被5整除,那么让他继续除以5; Step4.如果最后这个数变为1,那么这个数就是丑数,否则不是。

  根据以上算法实现代码如下:

    public int GetUglyNumber(int index)
    {
        if (index <= 0)
        {
            return 0;
        }

        int number = 0;
        int uglyCount = 0;

        while (uglyCount < index)
        {
            number++;

            if (IsUgly(number))
            {
                uglyCount++;
            }
        }

        return number;
    }

    private 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;
    }

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

2.2 空间换时间法:时间效率较高

  根据丑数的定义,我们可以知道丑数可以由另外一个丑数乘以2,3或者5得到。因此我们可以创建一个数组,里面的数字是排好序的丑数,每一个丑数都是前面的丑数乘以2,3或者5得到的。

  我们把得到的第一个丑数乘以2以后得到的大于M的结果记为M2。同样,我们把已有的每一个丑数乘以3和5,能得到第一个大于M的结果M3和M5。那么M后面的那一个丑数应该是M2,M3和M5当中的最小值:Min(M2,M3,M5)。比如将丑数数组中的数字按从小到大乘以2,直到得到第一个大于M的数为止,那么应该是2*2=4<M,3*2=6>M,所以M2=6。同理,M3=6,M5=10。所以下一个丑数应该是6。

  根据以上思路实现代码如下:

    public int GetUglyNumber(int index)
    {
        if (index <= 0)
        {
            return 0;
        }

        int[] uglyNumbers = new int[index];
        uglyNumbers[0] = 1;
        int nextUglyIndex = 1;

        int multiply2 = 0;
        int multiply3 = 0;
        int multiply5 = 0;
        int min = 0;

        while (nextUglyIndex < index)
        {
            min = Min(uglyNumbers[multiply2] * 2, uglyNumbers[multiply3] * 3, uglyNumbers[multiply5] * 5);
            uglyNumbers[nextUglyIndex] = min;

            while (uglyNumbers[multiply2] * 2 <= uglyNumbers[nextUglyIndex])
            {
                multiply2++;
            }

            while (uglyNumbers[multiply3] * 3 <= uglyNumbers[nextUglyIndex])
            {
                multiply3++;
            }

            while (uglyNumbers[multiply5] * 5 <= uglyNumbers[nextUglyIndex])
            {
                multiply5++;
            }

            nextUglyIndex++;
        }

        int result = uglyNumbers[index - 1];
        uglyNumbers = null;

        return result;
    }

    private int Min(int num1, int num2, int num3)
    {
        int min = num1 < num2 ? num1 : num2;
        min = min < num3 ? min : num3;

        return min;
    }

  和第一种方案相比,第二种方案不需要在非丑数的整数上做任何计算,因此时间效率有明显提升。但也需要指出,第二种算法由于需要保存已经生成的丑数,因此需要一个数组,从而增加了空间消耗。如果是求第1500个丑数,将创建一个能容纳1500个丑数的数组,这个数组占内存6KB。

三、单元测试与性能对比

3.1 单元测试

  (1)测试用例

    public static void Main(string[] args)
    {
        Program p = new Program();
        p.Test(1);
        p.Test(2);
        p.Test(3);
        p.Test(4);
        p.Test(5);
        p.Test(6);
        p.Test(7);
        p.Test(8);
        p.Test(9);
        p.Test(10);
        p.Test(11);
        p.Test(1500);
        p.Test(0);
        p.Test(1500);

        Console.ReadKey();
    }

    public void Test(int index)
    {
        int result = GetUglyNumberWithSpace(index);
        Console.WriteLine("Test result is {0}", result);
        Console.WriteLine("-------------End-------------");
    }

  (2)测试结果

3.2 性能对比

  这里我们使用两种解决方案来求第1500个丑数,通过下面的图片可以清楚地看到两种方案的响应时间。(这里借助老赵的CodeTimer类来进行时间效率的监测)

  (1)一一遍历法:65秒,我等得花儿都谢了

  (2)空间换时间法:4毫秒,迅雷不及掩耳

  由对比可以看出,一个简单的优化,再通过6KB的空间换取了巨大的时间效率,在实际开发中是一个值得实践的解决思路(当然,事先得权衡一下利弊)。

作者:周旭龙

出处:http://edisonchou.cnblogs.com

本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文链接。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏FSociety

SQL中GROUP BY用法示例

GROUP BY我们可以先从字面上来理解,GROUP表示分组,BY后面写字段名,就表示根据哪个字段进行分组,如果有用Excel比较多的话,GROUP BY比较类...

5.2K20
来自专栏web前端教室

你可以从面试中学到什么?

讲一下我对面试的一些。。。“偏见”,哈哈,熟悉我的同学们一定要批判的读接下来的内容哈。

12400
来自专栏haifeiWu与他朋友们的专栏

复杂业务下向Mysql导入30万条数据代码优化的踩坑记录

从毕业到现在第一次接触到超过30万条数据导入MySQL的场景(有点low),就是在顺丰公司接入我司EMM产品时需要将AD中的员工数据导入MySQL中,因此楼主负...

31040
来自专栏非著名程序员

「我真的没有改需求」

12210
来自专栏儿童编程

一张图理清《梅花易数》梗概

学《易经》的目的不一定是为了卜卦,但是了解卜卦绝对能够让你更好地了解易学。今天用一张思维导图对《梅花易数》的主要内容进行概括,希望能够给学友们提供帮助。

32640
来自专栏华章科技

穿越十年后看互联网+:家电行业的金矿在哪里?

现在市场上炒得火热的智能家居未来出路在何方?做智能家居的创业者应该注意哪些机会?传统家电厂商又到底如何借助互联网进行转型?本文以智能空调为例,用故事的形式,提前...

8410
来自专栏儿童编程

儿童创造力教育与编程教育的碰撞——MIT雷斯尼克教授最新理论梗概

儿童编程教育已经在我国各一线二线城市疯狂出现,颇有“烂大街”的趋势。我们不禁要问很多很多问题:

22870
来自专栏儿童编程

我不是算命先生,却对占卜有了疑惑——如何论证“占卜前提”的正确与否

事出有因,我对《周易》感兴趣了很多年。只是觉得特别有趣,断断续续学习了一些皮毛。这几天又偶然接触到了《梅花易数》,觉得很是精彩,将五行八卦天干地支都串联了起来。...

16010
来自专栏非著名程序员

这是对付产品经理的一副毒药,程序员慎入

程序员和产品经理的日常就像是一对天生的冤家,为了需求的实现,几乎天天在争吵。这不,就在昨天各大技术和产品群里一个程序员暴打产品经理的视频火了,被广泛传播。

12920
来自专栏Ken的杂谈

【系统设置】CentOS 修改机器名

18430

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励