丑数最快解法【python】

川长思鸟来 2022-04-08 08:29 401阅读 0赞

**题目描述**

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

--------------------

# 暴力算法 #

判断丑数的函数：

def isUglyNum(self, num):
         while num % 2 == 0:
             num /= 2
         while num % 3  == 0:
             num /= 3
         while num % 5 == 0:
             num /= 5
         if num == 1:
             return 1
         return 0

如果采用暴力的解法：

class Solution:
        def isUglyNum(self, num):
            while num % 2 == 0:
                num /= 2
            while num % 3  == 0:
                num /= 3
            while num % 5 == 0:
                num /= 5
            if num == 1:
                return 1
            return 0
        def GetUglyNumber_Solution(self, index):
            # write code here
            if index < 1:
                return 0
            if index == 1:
                return 1
            result = 1
            count = 1
            while True:
                result += 1
                if self.isUglyNum(result):
                    count += 1
                if count == index:
                    return result
    print(Solution().GetUglyNumber_Solution(1500))

**求1500个丑数肯定会超时**

--------------------

# 改进算法 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70]  
使用T2 T3 T5表示遍历的时候乘以2 3 5，需要遍历之前的每一个数字直到求出M2 M3 M5

class Solution:
        def GetUglyNumber_Solution(self, index):
            # write code here
            if index < 1:
                return 0
            if index == 1:
                return 1
            uglyNumberList = [1]
            T2 , T3, T5 = 0, 0, 0
            for i in range(1, index):
                if uglyNumberList[T2] * 2 <= uglyNumberList[i - 1]:
                    T2 += 1
                if uglyNumberList[T3] * 3 <= uglyNumberList[i - 1]:
                    T3 += 1
                if uglyNumberList[T5] * 5 <= uglyNumberList[i - 1]:
                    T5 += 1
                uglyNumber = min(uglyNumberList[T2] * 2, uglyNumberList[T3] * 3, uglyNumberList[T5] * 5) #M2 M3 M5
                uglyNumberList.append(uglyNumber)
            return uglyNumberList[index - 1]
    print(Solution().GetUglyNumber_Solution(1500))

输出：859963392

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70]: /images/20220407/31d54c601b7340ff881d0696b25fcd14.png