Leetcode 264. 丑数 II
题目描述
编写一个程序，找出第 n 个丑数。
丑数就是只包含质因数 2, 3, 5 的正整数。
示例 1:
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
说明
- 1 是丑数。
- n 不超过1690。
解法
丑数只包含质因数 2,3,5，即丑数由 2,3,5 与其他丑数相乘获得。因此可以维持一个递增丑数列表，将丑数列表中元素与 2,3,5 相乘的最小值作为新元素放入列表，直到获得第 n 个丑数。
可以给 2,3,5 三个数分别分配一个列表下标，在 2,3,5 与对应下标的元素相乘中选择最小值添加进列表，并修改下标指针，则可以依次获得丑数。
class Solution:
def nthUglyNumber(self, n: int) -> int:
arr,two,three,five=[1],0,0,0
for i in range(n-1):
tmp=min(arr[two]*2,arr[three]*3,arr[five]*5)
arr.append(tmp)
if arr[two]*2==tmp:
two+=1
if arr[three]*3==tmp:
three+=1
if arr[five]*5==tmp:
five+=1
return arr[-1]可能存在相乘后数值相等的情况，所以判断是否同时修改下标。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019.06.11 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读