面试题49. 丑数

题目

我们把只包含因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

示例:

输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
说明:

1 是丑数。
n 不超过1690。
注意：本题与主站 264 题相同：https://leetcode-cn.com/problems/ugly-number-ii/

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/chou-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

可以看成为是不同数量的 2 3 5 相乘，那我们每次只需要控制不同数量和按照大小顺序来就行了。

先上错误代码：

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        if n == 1: return 1
        i,j,k = 0,0,0
        while n-1 > 0:
            n -= 1
            I,J,K = 2**(i+1)*3**j*5**k,2**i*3**(j+1)*5**k,2**i*3**j*5**(k+1)
            if I<J and I<K:
                i += 1
            if J<K and J<I:
                j+=1
            if K<I and K<J:
                k+=1
            print(i,j,k)
        return 2**i*3**j*5**k

问题在哪呢，while循环中每次都是基于上一次的数字计算，也就是每次都会选择*2.

实际上我们想要的效果是这样：也就是第三个数字不是基于第二个数，而是基于第一个。

动态规划！每次向前推进一点点，对 2 3 5 分别设置一个指针指向数组，比如2 指向的数字，每乘一次2就移动一格。

为了防止重复，比如6既是2的倍数也是3的倍数，所以两指针都要+1

代码

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        nums = [0]*1690
        nums[0] = 1
        p2, p3, p5 = 0, 0, 0
        for i in range(1,1690):
            nums[i] = min(2*nums[p2],3*nums[p3],5*nums[p5])
            # 不能用else不然会出现重复
            if nums[i] == 2*nums[p2] : p2 += 1
            if nums[i] == 3*nums[p3] : p3+=1
            if nums[i] == 5*nums[p5] : p5+=1
        return nums[n-1]