剑指Offer面试题：29.丑数

2022-03-26 23:04:10

一、题目：丑数

题目：我们把只包含因子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 <= )

        {

            return ;

        }

        int number = ;

        int uglyCount = ;

        while (uglyCount < index)

        {

            number++;

            if (IsUgly(number))

            {

                uglyCount++;

            }

        }

        return number;

    }

    private bool IsUgly(int number)

    {

        while (number %  == )

        {

            number /= ;

        }

        while (number %  == )

        {

            number /= ;

        }

        while (number %  == )

        {

            number /= ;

        }

        return number ==  ? true : false;

    }

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

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

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

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

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

    public int GetUglyNumber(int index)

    {

        if (index <= )

        {

            return ;

        }

        int[] uglyNumbers = new int[index];

        uglyNumbers[] = ;

        int nextUglyIndex = ;

        int multiply2 = ;

        int multiply3 = ;

        int multiply5 = ;

        int min = ;

        while (nextUglyIndex < index)

        {

            min = Min(uglyNumbers[multiply2] * , uglyNumbers[multiply3] * , uglyNumbers[multiply5] * );

            uglyNumbers[nextUglyIndex] = min;

            while (uglyNumbers[multiply2] *  <= uglyNumbers[nextUglyIndex])

            {

                multiply2++;

            }

            while (uglyNumbers[multiply3] *  <= uglyNumbers[nextUglyIndex])

            {

                multiply3++;

            }

            while (uglyNumbers[multiply5] *  <= uglyNumbers[nextUglyIndex])

            {

                multiply5++;

            }

            nextUglyIndex++;

        }

        int result = uglyNumbers[index - ];

        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();

        p.Test();

        p.Test();

        p.Test();

        p.Test();

        p.Test();

        p.Test();

        p.Test();

        p.Test();

        p.Test();

        p.Test();

        p.Test();

        p.Test();

        p.Test();

        Console.ReadKey();

    }

    public void Test(int index)

    {

        int result = GetUglyNumberWithSpace(index);

        Console.WriteLine("Test result is {0}", result);

        Console.WriteLine("-------------End-------------");

    }