题解 | #丑数 python#

• 事实上我们不需要每次都计算前面所有丑数乘以2，3，5的结果，然后再比较大小。因为在已存在的丑数中，一定存在某个数m2（在代码中用res[t2]表示，t2表示需要乘以2的丑数的位置），在它之前的所有数乘以2都小于已有丑数，
  而m2×2的结果一定大于最大的丑数，同理，也存在这样的数m3，m5，我们只需要标记这三个数即可。

class Solution:
    def GetUglyNumber_Solution(self, index):
        if index == 0:
            return 0
        res = [1]  # res用来存储丑数
        t2 = t3 = t5 = 0  # 标记位置
        for i in range(index - 1):
            min_num = min(res[t2] * 2, res[t3] * 3, res[t5] * 5)
            # 将res中的第0个元素1分别2,3,5，然后取最小的一个数2放到res中
            res.append(min_num)
            # 判断res中最大丑数前的丑数k乘以2,3,5是不是小于最大的丑数，
            # 小于则说明该丑数k已经乘过2或3,或5了，那么它的位置t就必须往后移一个
            if res[t2] * 2 <= min_num:
                t2 += 1
            if res[t3] * 3 <= min_num:
                t3 += 1
            if res[t5] * 5 <= min_num:
                t5 += 1
        return res[-1]
s = Solution()
print(s.GetUglyNumber_Solution(7))