【剑指offer】丑数

题目描述

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

解决方案

1.一一遍历：时间复杂度高

一次遍历求出第index个丑数，从1开始，如果是丑数则count++，直到count = index为止。判断丑数依据题目意思，丑数只有2,3,5三个因子，因此就用这个数除以这个3个因子

1.如果一个数能够被2整除，那么就让他继续除以2
2.如果一个数能够被3整除，那么就让他继续除以3
3.如果一个数能够被5整除，那么就让他继续除以5
4.如果这个数最终变成了1，那么这个数就是丑数

根据以上定义实现代码如下：

class Solution {
public:
    int GetUglyNumber_Solution(int index) {
        if(index <1)
            return 0;
        int number = 0;
        int uglyCount = 0;
        while(uglyCount < index)
        {
            number++;
            if(IsUgly(number))
            {
                uglyCount++;
            }
        }
        return number;
    }
    
    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以后得到的大于M的结果记为M2。同样，我们把已有的每一个丑数乘以3和5，能得到第一个大于M的结果M3和M5。那么M后面的那一个丑数应该是M2,M3和M5当中的最小值：Min(M2,M3,M5)。比如将丑数数组中的数字按从小到大乘以2，直到得到第一个大于M的数为止，那么应该是22=4<M，32=6>M，所以M2=6。同理，M3=6，M5=10。所以下一个丑数应该是6。

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

class Solution{
public:
    int GetUglyNumber_Solution(int index) {
        if(index<1)
            return 0;
        int uglyNumbers[index];
        uglyNumbers[0] = 1;
        int nextUglyIndex = 1;
        int mutiply2 = 0;
        int mutiply3 = 0;
        int mutiply5 = 0;
        
        int min = 0;
        
        while(nextUglyIndex < index)
        {
            min = Min(uglyNumbers[mutiply2]*2,uglyNumbers[mutiply3]*3,uglyNumbers[mutiply5]*5);
            uglyNumbers[nextUglyIndex] = min;
            
            while(uglyNumbers[mutiply2]*2 <= uglyNumbers[nextUglyIndex])
            {
                mutiply2++;
            }
            while(uglyNumbers[mutiply3]*3 <= uglyNumbers[nextUglyIndex])
            {
                mutiply3++;
            }
            while(uglyNumbers[mutiply5]*5 <= uglyNumbers[nextUglyIndex])
            {
                mutiply5++;
            }
            nextUglyIndex++;
        }
        int result = uglyNumbers[index-1];
        return result;
        
    }
        int Min(int num1,int num2,int num3)
        {
            int min = num1<num2?num1:num2;
            min = min<num3?min:num3;
            return min;
        }
};