方案一：最小堆。
    方案二：三指针法。

    1. # 编写一个程序，找出第 n 个丑数。 
    2. # 
    3. #  丑数就是质因数只包含 2, 3, 5 的正整数。 
    4. # 
    5. #  示例: 
    6. # 
    7. #  输入: n = 10
    8. # 输出: 12
    9. # 解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。 
    10. # 
    11. #  说明: 
    12. # 
    13. #  
    14. #  1 是丑数。 
    15. #  n 不超过1690。 
    16. #  
    17. #  Related Topics 堆 数学 动态规划 
    18. #  👍 361 👎 0
    20. from heapq import *
    23. # leetcode submit region begin(Prohibit modification and deletion)
    24. class Solution(object):
    25.     def nthUglyNumber(self, n):
    26.         """
    27.         :type n: int
    28.         :rtype: int
    29.         """
    31.         num = [1]
    32.         p2 = p3 = p5 = 0
    33.         while len(num) < n:
    34.             ugly = min(num[p2] * 2, num[p3] * 3, num[p5] * 5)
    35.             num.append(ugly)
    36.             if ugly == num[p2] * 2:
    37.                 p2 += 1
    38.             if ugly == num[p3] * 3:
    39.                 p3 += 1
    40.             if ugly == num[p5] * 5:
    41.                 p5 += 1
    42.         return num[n - 1]
    45. # leetcode submit region end(Prohibit modification and deletion)
    47. s = Solution()
    48. print(s.nthUglyNumber(10))