丑数.md

丑数

知识点：

题目描述

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

解题思路

如果p是丑数，那么$p=2^x \times 3^y \times5^z$ 所以，我们只需要寻找不同的x、y、z进而寻找到不同的丑数.

具体实现思路是使用三个指针t2，t3，t5记录最新一个乘了2、3、5对应的丑数，下一个丑数应该是$min(t2\times2,t3\times3,t5\times5)$,得到的结果就是下一个丑数，以此类推即可得到第N个丑数。

代码

    def GetUglyNumber_Solution(self, index):
        # write code here
        if index==0:
            return 0

        t2Index = 0
        t3Index = 0
        t5Index = 0

        res = [1]

        for i in range(0, index - 1):
            minValue = min(res[t2Index] * 2, min(res[t3Index] * 3, res[t5Index] * 5))
            res.append(minValue)
            if minValue == res[t2Index] * 2:
                t2Index += 1
            if minValue == res[t3Index] * 3:
                t3Index += 1
            if minValue == res[t5Index] * 5:
                t5Index += 1

        return res[-1]

这里