题解 | #丑数#

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

方法一：暴力求解

求解思路
对于求解丑数，因为题目要求丑数的质因子只能为2，3，5.根据整数可以唯一被质数表示可知，我们采用枚举的方法，直接将 中的i，j，k直接循环即可。最后再将得到的数组进行排序，即可求出最后的答案。

解题代码

class Solution {
public:
    int p[11111111];//存储枚举数组的结果，可以随便设置一个比较大的长度。
    int GetUglyNumber_Solution(int index) {
    p[1]=1;
    int x=2;
    for(int i=0;i<=50;i++)
    {
        for(int j=0;j<=50;j++)
        {
            for(int k=0;k<=50;k++)
            {
                if (i==0 && j==0 && k==0) continue;
                int t=pow(2,i)*pow(3,j)*pow(5,k);
                if (t<0)continue;
                p[x++]=t;
            }
        }
    }
    sort(p,p+x);//对求出的所有丑数进行排序，最后输出结果即可。
    return p[index];
    }
};

复杂度分析
时间复杂度：三个for循环，O( )
空间复杂度：一个常数级数组来存储丑数，因此空间复杂度为O(1)

方法二：最小堆的思想、参考复旦大学呼口周哼的解法

求解思路
一开始将1放入最小堆，然后取出堆顶元素（1）分别乘2，3，5.并且新的数字入堆，并且在入堆的过程中将重复的数字去除，最后将堆构建好，按题目要求取出第n个元素即可。

解题代码

import heapq
class Solution:
    def GetUglyNumber_Solution(self, index):
        if index <= 0:
            return 0
        myf = [2,3,5]
        heap = [1]
        check = [1]

        for i in range(index - 1):
            cur = heapq.heappop(heap)
            for f in myf:
                n = cur * f
                if n not in check:
                    check.append(n)
                    heapq.heappush(heap, n)
        return heapq.heappop(heap)

复杂度分析
时间复杂度：堆排序时间，O(nlogn)
空间复杂度：因为构建堆花费了额外的内存空间，因此复杂度为O(n)