'''
思路：
不是逐个对每个数判断
类似于素数埃氏筛（本质是批量删除不符合条件的元素，获得剩下的元素集合）
本题则是批量生成符合条件的元素，获取元素集合

每个丑数必然是由小于它的某个丑数乘以2，3或5得到的
un：每个丑数*n的集合
三路归并，求u2、u3、u5的交集
由于u2、u3、u5、f共享同一个下标，所以可以使用同一个集合就行，只是u2、u3、u5的元素需要对f相应计算获得
f[i]第i个丑数，i从0开始
f[i] = min(f[u2]*2, f[u3]*3, f[u5]*5)
找出这三这种最小的并且大于当前最大丑数的值，即为下一个我们要求的丑数。
'''

class Solution(object):
    def getUglyNumber(self, n):
        """
        :type n: int
        :rtype: int
        """
        f = [1]
        u2, u3, u5 = 0, 0, 0
        for i in range(1, n):
            f.append(min(f[u2]*2, f[u3]*3, f[u5]*5))
            if f[i] == f[u2]*2: u2 += 1
            if f[i] == f[u3]*3: u3 += 1
            if f[i] == f[u5]*5: u5 += 1
        return f[n-1]