【leetcode刷题】T46-丑数 II
【英文题目】（学习英语的同时，更能理解题意哟~）
Write a program to find the n-th ugly number.
Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.
Example:
Input: n = 10
Output: 12
Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.
Note:
1is typically treated as an ugly number.ndoes not exceed 1690.
【中文题目】
编写一个程序，找出第 n 个丑数。
丑数就是只包含质因数 2, 3, 5 的正整数。
示例:
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
说明:
1是丑数。n不超过1690。
【思路】
第一种方法，暴力破解，从1开始遍历，判断数是否为丑数。时间复杂度太高。
第二种方法，申请个数组，下标作为数，存储信息为是否是丑数的标签。首先设置所有标签为false（1为true），遍历数组，当标签为true，将该数的2倍、3倍、5倍标为true。但是，循环的截止条件不好定义。
第三种方法，下一个丑数必定是前面某一个丑数的2倍、3倍或者5倍。我们用i2、i3、i5分别存储最后一个满足条件的使用2倍、3倍和5倍的元素下标，下一个丑数为min(ls[i2]*2, ls[i3]*3, ls[i5]*5)。（见代码）
【代码】
python版本
复杂但易理解的方法
class Solution(object):
def nthUglyNumber(self, n):
"""
:type n: int
:rtype: int
"""
count =
ls = []
d = {:}
while count < n:
if ls[count] * not in d:
ls.append(ls[count] * )
d[ls[count] * ] =
if ls[count] * not in d:
ls.append(ls[count] * )
d[ls[count] * ] =
if ls[count] * not in d:
ls.append(ls[count] * )
d[ls[count] * ] =
ls.sort()
count +=
return ls[n-1]
方法三
class Solution(object):
def nthUglyNumber(self, n):
"""
:type n: int
:rtype: int
"""
i2 = i3 = i5 =
ls = []
while len(ls) < n:
while ls[i2] * <= ls[-1]: i2 +=
while ls[i3] * <= ls[-1]: i3 +=
while ls[i5] * <= ls[-1]: i5 +=
ls.append(min(ls[i2]*, ls[i3]*, ls[i5]*))
return ls[n-1]
C++版本
class Solution {
public:
int nthUglyNumber(int n) {
int i2=, i3=, i5=;
vector<int> ls(,);
while(ls.size() < n){
while(ls[i2] * <= ls[ls.size()-1]) i2++;
while(ls[i3] * <= ls[ls.size()-1]) i3++;
while(ls[i5] * <= ls[ls.size()-1]) i5++;
ls.push_back(min(min(ls[i2]*, ls[i3]*), ls[i5]*));
}
return ls[ls.size()-1];
}
};本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-04-21，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读