题解 | #丑数#

丑数

http://www.nowcoder.com/practice/6aa9e04fc3794f68acf8778237ba065b

思路

根据题中定义，我们了解到丑数都是可以拆分为 2^x*3^y*5^z 的数字，因此思路集中在解决质因数的分解问题上，如何巧妙地利用质因数会衍生出不同的思路

暴力解法（超时）：直接判断每一个自然数是否是符合丑数的质因数分解规律
最小堆解法：维护一个丑数最小堆，每次从堆顶取出当前最小值i，并再将2i,3i,5i重新入堆，按照取出值的顺序得到目标值
动态规划方法：最小堆的方案是将存入数据结构后再排序，动态规划是将数字排序后按顺序存入，因此有转移方程 dp[i]=min(dp[p_2]*2,dp[p_3]*3,dp[p_5]*5)

方法一：暴力解法（超时）

具体做法：先构造一个Judge函数来帮助判断是否为丑数，再通过循环遍历自然数，直到找到目标个数的最终数字。

# -*- coding:utf-8 -*-
class Solution:
    def Judge(n):
        if n <= 0:
            return 0
        while (n % 2) == 0:        #将质因子2全部除干净
            n /= 2
        while (n % 3) == 0:        #将质因子3全部除干净
            n /= 3
        while (n % 5) == 0:        #将质因子5全部除干净
            n /= 5
        return n == 1              #如果最终结果为1说明该数n是丑数
    def GetUglyNumber_Solution(self, index):
        # write code here
        if index <= 0:                      #特殊条件处理
            return 0
        num = 0
        count = 0
        while count < index:                #进行遍历暴力搜索
            if Solution.Judge(num):
                count += 1                  #直到搜索到一个丑数后计数器+1
            num += 1
        return num - 1

复杂度分析

时间复杂度：O(nlogn)，粗略认为Judge函数中三个循环都时间复杂度各为logn
空间复杂度：O(1)，无额外空间申请

方法二：最小堆

具体做法：
初始时候最小堆将第一个丑数1入堆。
取出堆顶元素 x，并将 2x,3x,5x 入堆，并在入堆前处理去重问题
取出的第n个元素即最终所求

# -*- coding:utf-8 -*-
import heapq
class Solution:
    def GetUglyNumber_Solution(self, index):
        # write code here
        if index <= 0:
            return 0
        ff = [2,3,5]                                  #维护一个质因子2,3,5的数组便于计算
        heap = [1]                                    #维护堆
        check = [1]                                   #检查是否已经出现过

        for i in range(index - 1):
            cur = heapq.heappop(heap)                 #取最小堆堆顶元素
            for f in ff:                              #和质因子分别相乘
                n = cur * f
                if n not in check:                    #去掉重复出现的元素
                    check.append(n)
                    heapq.heappush(heap, n)           #乘积结果重新进堆
        return heapq.heappop(heap)                    #返回最小堆堆顶

复杂度分析

时间复杂度：O(nlogn)，其中堆排序时间O(logn)
空间复杂度：O(n)，维护了堆结构

方法三：动态规划（贪心取最小）

定义数组uglyNum，其中uglyNum[i]表示第i个丑数，求第n个丑数的最终返回结果为uglyNum[n]
定义三个指针索引，表示当前的丑数。将当前丑数乘上对应的质因数得到下一个待选的丑数
将三个带选丑数进行比较选出最小值，作为最终的下一个丑数，并将进行乘法操作的对应指针+1
其实就相当于维护了三个数组，分别是乘2,3,5的递增数组，每个数组的第一个数都是1。将三个数组最终合并成为一个严格递增的数组，在各个数组内不断移动指针并计算各个数组内的下一个数值，一直循环这一过程直到得到最终结果。

# -*- coding:utf-8 -*-
class Solution:
    def GetUglyNumber_Solution(self, index):
        # write code here
        if index <= 0:                                                        #处理特殊情况
            return 0
        uglyNum = [1]                                                         #维护最终丑数的数组
        id1 = id2 = id3 = 0                                                   #三个指针分别对应2,3,5质因数的乘积数组索引
        for i in range(index - 1):
            nextVal = min(uglyNum[id1]*2, uglyNum[id2]*3, uglyNum[id3]*5)     #贪心选取三者乘积最小的元素
            uglyNum.append(nextVal)                                           #将最小元素添加到丑数数列最后
            if(uglyNum[-1] == uglyNum[id1]*2):                                #相应的三组索引指针houy
                id1 += 1
            if(uglyNum[-1] == uglyNum[id2]*3):
                id2 += 1
            if(uglyNum[-1] == uglyNum[id3]*5):
                id3 += 1
        return uglyNum[-1]