把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第 n个丑数。
数据范围：
要求：空间复杂度 )
， 时间复杂度
[编程题]丑数
class Solution: def GetUglyNumber_Solution(self, index): # write code here res = [0]*index x,y,z = 0,0,0 if index <=6: return index n = index res[0] = 1 for i in range(1,n): res[i] = min(2*res[x],min(3*res[y],5*res[z])) if res[i] == 2*res[x]: x+=1 if res[i] == 3*res[y]: y+=1 if res[i] == 5*res[z]: z+=1 return res[index-1]理解算法本身通过题解一开始，两次min（）得到res对应位置上的值
发表于 2021-08-21 16:09:07
回复(0)
# -*- coding:utf-8 -*-
class Solution:
def GetUglyNumber_Solution(self, index):
# write code here
if not index:
return 0
res = [1]
array = []
while len(res) < index:
# 丑数一定是前面的丑数乘以2，3，5得到的
for i in [res[-1]*2, res[-1]*3, res[-1]*5]:
if i not in array:
array.append(i)
next_ugly = min(array)
res.append(next_ugly)
array.remove(next_ugly)
return res[-1]
发表于 2021-06-07 21:49:09
回复(0)
class Solution:
def GetUglyNumber_Solution(self, index):
# write code here
if index <= 1:
return index
res = [1]
T1 , T2, T3 = 2 , 3 , 5
num1 , num2 , num3 = 0 , 0 , 0
for i in range(1 ,index):
cur_value = min(res[num1]*2 , res[num2]*3 , res[num3]*5)
res.append(cur_value)
if cur_value % T1 == 0:
num1 += 1
if cur_value % T2 == 0:
num2 += 1
if cur_value % T3 == 0:
num3 += 1
return res[-1]
def GetUglyNumber_Solution(self, index):
# write code here
if index <= 1:
return index
res = [1]
T1 , T2, T3 = 2 , 3 , 5
num1 , num2 , num3 = 0 , 0 , 0
for i in range(1 ,index):
cur_value = min(res[num1]*2 , res[num2]*3 , res[num3]*5)
res.append(cur_value)
if cur_value % T1 == 0:
num1 += 1
if cur_value % T2 == 0:
num2 += 1
if cur_value % T3 == 0:
num3 += 1
return res[-1]
发表于 2021-05-12 17:30:32
回复(0)
Python 丑数由x个2，y个3，z个5相乘得到，维护三个数组，每次选择最小的加入有序丑数数列，注意这个数要从三个数列中删除（可能有重复）。特殊情况是index=0时返回0。
# -*- coding:utf-8 -*- class Solution: def GetUglyNumber_Solution(self, index): # write code here if index<1: return 0 uglynums = [1] ugly_2 = [] ugly_3 = [] ugly_5 = [] for i in range(1,index): ugly_2.append(uglynums[-1]*2) ugly_3.append(uglynums[-1]*3) ugly_5.append(uglynums[-1]*5) min_ugly = min(ugly_2[0],ugly_3[0],ugly_5[0]) uglynums.append(min_ugly) if min_ugly==ugly_2[0]: ugly_2.pop(0) if min_ugly==ugly_3[0]: ugly_3.pop(0) if min_ugly==ugly_5[0]: ugly_5.pop(0) return uglynums[-1]
发表于 2021-04-17 20:15:16
回复(0)
超时。。。
# -*- coding:utf-8 -*- class Solution: def GetUglyNumber_Solution(self, index): if index <= 1: return index result = [] length, point = 0,1 while length < index: length += 1 result.append(point) temp = point while temp % 5 == 0: temp = temp / 5 while temp % 3 == 0: temp = temp / 3 while temp % 2 == 0: temp = temp / 2 if temp > 5: result.pop() length -= 1 point += 1 return result[index-1]
发表于 2021-04-08 10:43:00
回复(0)
python解法：
# -*- coding:utf-8 -*-
'''
解法1：动态规划，思想：
丑数*丑数=丑数；
假设当前存在3个数组nums2,nums3,nums5分别代表丑数序列从1开始分别乘以2,3,5的序列，即：
nums2 = {1*2, 2*2, 3*2, 4*2, 5*2, 6*2, 8*2...}
nums3 = {1*3, 2*3, 3*3, 4*3, 5*3, 6*3, 8*3...}
nums5 = {1*5, 2*5, 3*5, 4*5, 5*5, 6*5, 8*5...}
选择最小的n个；
'''
class Solution:
def GetUglyNumber_Solution(self, index):
if index == 0:
return 0
dp = [1] * index
a,b,c = 0,0,0
for i in range(1,index): # 从dp[1]开始；
n2,n3,n5 = dp[a]*2,dp[b]*3,dp[c]*5
dp[i] = min(n2,n3,n5) # 每次选择最小的丑数；
if dp[i] == n2:
a += 1
if dp[i] == n3:
b += 1
if dp[i] == n5:
c += 1
# print(dp[i])
return dp[index-1]
编辑于 2021-02-20 15:47:34
回复(0)
# -*- coding:utf-8 -*- class Solution: def GetUglyNumber_Solution(self, index): # write code here if index < 1: return 0 res = [1] t2 = 0 t3 = 0 t5 = 0 while index-1: # 因为index从1开始计数 res.append(min(res[t2]*2, res[t3]*3, res[t5]*5)) while res[t2]*2 <= res[-1]: t2 += 1 while res[t3]*3 <= res[-1]: t3 += 1 while res[t5]*5 <= res[-1]: t5 += 1 index -= 1 return res[-1]
发表于 2020-10-14 21:24:39
回复(0)
# -*- coding:utf-8 -*- class Solution: def GetUglyNumber_Solution(self, index): # write code here if index<1: return 0 list = [1] twopointer = 0 threepointer = 0 fivepointer = 0 count = 0 while count != index: minValue = min(2*list[twopointer],3*list[threepointer],5*list[fivepointer]) list.append(minValue) count +=1 if minValue == 2*list[twopointer]: twopointer +=1 if minValue == 3*list[threepointer]: threepointer +=1 if minValue == 5*list[fivepointer]: fivepointer +=1 return list[count-1]讲*2、*3、*5的指针开始都指向第一个数，然后比较结果，将最小的依次放入后面。
发表于 2020-08-05 15:36:54
回复(0)
设定三个游标，指向对应的数（初始都指向第一个数），并分别执行*2、*3、*5操作，哪个数最小就在list中插入，作为下一个丑数。
class Solution: def GetUglyNumber_Solution(self, index): # write code here if index<=0: return 0 l=[1] point_2=0 point_3=0 point_5=0 count=1 while count!=index: l.append(min(2*l[point_2],3*l[point_3],5*l[point_5])) count+=1 if 2*l[point_2]==l[-1]: point_2+=1 if 3*l[point_3]==l[-1]: point_3+=1 if 5*l[point_5]==l[-1]: point_5+=1 return l[-1]
发表于 2020-03-15 10:53:09
回复(0)
# -*- coding:utf-8 -*- # 只需要把得到的丑数不断地乘以2、3、5之后并放入他们应该放置的位置即可， # 而此题的难点就在于如何有序的放在合适的位置。 # 1乘以 （2、3、5）=2、3、5；2乘以（2、3、5）=4、6、10；3乘以（2、3、5）=6,9,15；5乘以（2、3、5）=10、15、25； # 从这里我们可以看到如果不加策略地添加丑数是会有重复并且无序， # 而在2x，3y，5z中，如果x=y=z那么最小丑数一定是乘以2的，但关键是有可能存在x》y》z的情况， # 所以我们要维持三个指针来记录当前乘以2、乘以3、乘以5的最小值，然后当其被选为新的最小值后，要把相应的指针+1； # 因为这个指针会逐渐遍历整个数组，因此最终数组中的每一个值都会被乘以2、乘以3、乘以5，也就是实现了我们最开始的想法， # 只不过不是同时成乘以2、3、5，而是在需要的时候乘以2、3、5. class Solution: def GetUglyNumber_Solution(self, index): # write code here if index == 1: return 1 res = [1] i2 = 0 i3 = 0 i5 = 0 for i in range(index - 1): m = min(res[i2] * 2, res[i3] * 3, res[i5] * 5) res.append(m) if m % 2 == 0: i2 += 1 if m % 3 == 0: i3 += 1 if m % 5 == 0: i5 += 1 return res[-1]
发表于 2019-12-07 12:50:57
回复(0)
class Solution: def GetUglyNumber_Solution(self, index): # write code here if index <= 0: return 0 # 储存丑数 ugly_list = [1] # 指针标明这是第几个丑数 pointer = 0 # 乘2 的指针 pointer2 = 0 # 乘3 的指针 pointer3 = 0 # 乘5 的指针 pointer5 = 0 # 直到 第index 个丑数 终止 while pointer < index-1: # 确保 指针指向的是第一个超过丑数的丑数 while 2 * ugly_list[pointer2] <= ugly_list[pointer]: pointer2 += 1 while 3 * ugly_list[pointer3] <= ugly_list[pointer]: pointer3 += 1 while 5 * ugly_list[pointer5] <= ugly_list[pointer]: pointer5 += 1 # 比较哪个丑数最小 就是下一个 next_num = min(2 * ugly_list[pointer2], 3 * ugly_list[pointer3], 5 * ugly_list[pointer5]) # 存上 ugly_list.append(next_num) # 多了一个丑数 pointer += 1 return ugly_list[-1]
发表于 2019-11-09 01:23:50
回复(0)
动态规划,每次用之前求得的丑数更新其与2,3,5的乘积
# -*- coding:utf-8 -*- class Solution: def GetUglyNumber_Solution(self, index): if index==0: return 0 res=[0]*index res[0]=1 t2=t3=t5=0 if index>1: for i in range(1,index): res[i]=min(res[t2]*2,res[t3]*3,res[t5]*5) if res[t2]*2==res[i]: t2+=1 if res[t3]*3==res[i]: t3+=1 if res[t5]*5==res[i]: t5+=1 return res[-1]
发表于 2019-11-05 18:45:57
回复(0)
# -*- coding:utf-8 -*-
class Solution:
def GetUglyNumber_Solution(self, index):
uglynum = [1]
n = index
i = 1
t2 = m2 = 0
t3 = m3 = 0
t5 = m5 = 0
if n==0:
return 0
if n==1:
return uglynum[-1]
else:
while i < n:
for x in range(t2, len(uglynum)):
m2 = uglynum[x] * 2
if m2 > uglynum[-1]:
t2 = x
break
for x in range(t3, len(uglynum)):
m3 = uglynum[x] * 3
if m3 > uglynum[-1]:
t3 = x
break
for x in range(t5, len(uglynum)):
m5 = uglynum[x] * 5
if m5 > uglynum[-1]:
t5 = x
break
uglynum.append(min(m2, m3, m5))
i = i + 1
return uglynum[-1] # write code here
class Solution:
def GetUglyNumber_Solution(self, index):
uglynum = [1]
n = index
i = 1
t2 = m2 = 0
t3 = m3 = 0
t5 = m5 = 0
if n==0:
return 0
if n==1:
return uglynum[-1]
else:
while i < n:
for x in range(t2, len(uglynum)):
m2 = uglynum[x] * 2
if m2 > uglynum[-1]:
t2 = x
break
for x in range(t3, len(uglynum)):
m3 = uglynum[x] * 3
if m3 > uglynum[-1]:
t3 = x
break
for x in range(t5, len(uglynum)):
m5 = uglynum[x] * 5
if m5 > uglynum[-1]:
t5 = x
break
uglynum.append(min(m2, m3, m5))
i = i + 1
return uglynum[-1] # write code here
发表于 2019-10-06 18:23:45
回复(0)
# -*- coding:utf-8 -*- class Solution: def GetUglyNumber_Solution(self, index): # write code here if index==0: return 0 if index==1: return 1 res=[0,1] i2,i3,i5=1,1,1 while index>1: x,y,z=res[i2]*2,res[i3]*3,res[i5]*5 if min(x,y,z)==x: tar=x i2+=1 elif min(x,y,z)==y: tar=y i3+=1 else: tar=z i5+=1 if tar!=res[-1]: res.append(tar) index-=1 return res[-1]
发表于 2019-10-05 16:58:45
回复(0)
# -*- coding:utf-8 -*-
class Solution:
def GetUglyNumber_Solution(self, index):
# write code here
def Min(a,b,c):
if a>b:
min=b
else:
min=a
if min>c:
min=c
return min
if(index<=0):
return 0
list1=[]
list1.append(1)
nextindex=1
mul2=list1[0]
mul3=list1[0]
mul5=list1[0]
i=j=k=0
while(nextindex<index):
#每次数组都增加最小的丑数
min=Min(mul2*2,mul3*3,mul5*5)
list1.append(min)
#每次修改最小的基数
while(mul2*2<=min):
mul2=list1[i]
i=i+1
while(mul3*3<=min):
mul3=list1[j]
j=j+1
while(mul5*5<=min):
mul5=list1[k]
k=k+1
nextindex=nextindex+1
return list1[index-1]
class Solution:
def GetUglyNumber_Solution(self, index):
# write code here
def Min(a,b,c):
if a>b:
min=b
else:
min=a
if min>c:
min=c
return min
if(index<=0):
return 0
list1=[]
list1.append(1)
nextindex=1
mul2=list1[0]
mul3=list1[0]
mul5=list1[0]
i=j=k=0
while(nextindex<index):
#每次数组都增加最小的丑数
min=Min(mul2*2,mul3*3,mul5*5)
list1.append(min)
#每次修改最小的基数
while(mul2*2<=min):
mul2=list1[i]
i=i+1
while(mul3*3<=min):
mul3=list1[j]
j=j+1
while(mul5*5<=min):
mul5=list1[k]
k=k+1
nextindex=nextindex+1
return list1[index-1]
发表于 2019-08-11 19:30:31
回复(0)
# -*- coding:utf-8 -*-
class Solution:
def GetUglyNumber_Solution(self, index):
# write ,code here
if index <= 0:
return 0
ans =[1]
i2= i3= i5 =0
i=0
while i<index:
# 每可执行一次while，ans的长度加一；执行到最后，当i=index时不执行
i+=1
ans.append(min(ans[i2]*2, ans[i3]*3, ans[i5]*5))
if ans[i]==ans[i2]*2:
i2+=1
if ans[i]==ans[i3]*3:
i3+=1
if ans[i]==ans[i5]*5:
i5+=1
return ans[i-1] # =ans[index-1]
发表于 2019-07-23 11:19:03
回复(0)
""" 我是Python届的耻辱，竟然写了这么多行 Run time: 68ms Date: 2019-07-11 傍晚 模拟前面大神设置队列标准的解法，就是实现的太复杂啦，我好笨呀 """ # -*- coding:utf-8 -*- class Solution: def GetUglyNumber_Solution(self, index): # write code here if index == 1: return 1 if index == 0: return 0 ugly = 1 list1 = [2] list2 = [3] list3 = [5] for i in range(2,index+1): ugly = min(sorted(list1)[0], sorted(list2)[0], sorted(list3)[0]) ugly1 = ugly * 2 ugly2 = ugly * 3 ugly3 = ugly * 5 if ugly == list1[0]: list1.pop(0) if ugly1 not in list1: list1.append(ugly1) if ugly2 not in list2: list2.append(ugly2) if ugly3 not in list3: list3.append(ugly3) if ugly == list2[0]: list2.pop(0) if ugly1 not in list1: list1.append(ugly1) if ugly2 not in list2: list2.append(ugly2) if ugly3 not in list3: list3.append(ugly3) if ugly == list3[0]: list3.pop(0) if ugly1 not in list1: list1.append(ugly1) if ugly2 not in list2: list2.append(ugly2) if ugly3 not in list3: list3.append(ugly3) return ugly
编辑于 2019-07-11 18:21:54
回复(0)
（1）设置数组 UglyNum=[] 用来保存丑数。并将 1 添加进数组 UglyNum=[1]。基数设置为 2,3,5 。以基数为质因子的丑数的下标为 id2,idx3,idx5 ，起始均为 0 。 （2）计算： 2×UglyNum[idx2]=2×1,3×UglyNum[idx3]=3×1，5×UglyNum[idx5]=5×1 ，将最小的数存入数组 UglyNum=[1,2] ,以 2 为基数的丑数下标增加 1 ： idx2=0+1=1 ，其余不变。 （3）计算： 2×UglyNum[idx2]=2×1,3×UglyNum[idx3]=3×1,5×UglyNum[idx5]=5×1 ，将最小的数存入数组 UglyNum=[1,2,3] ,以 3 为基数的丑数下标增加 1 ： idx3=0+1=1 ，其余不变。 （4）计算： 2×UglyNum[idx2]=2×2,3×UglyNum[idx3]=3×2,5×UglyNum[idx5]=5×1 , 将最小的数存入数组 UglyNum=[1,2,3,4] ,以 2 为基数的丑数下标增加 1 ： idx2=1+1=2 ，其余不变。 （5）计算： 2×UglyNum[idx2]=2×3,3×UglyNum[idx3]=3×2，5×UglyNum[idx5]=5×1 , 将最小的数存入数组 UglyNum=[1,2,3,4,5] ,以 5 为基数的丑数下标增加 1 ： idx5=0+1=1 ，其余不变。 （6）以此类推，计算 n−1 次，并将值存入数组中。返回数组最后一个值即为所求。
发表于 2019-05-16 20:19:13
回复(0)
def GetUglyNumber_Solution(self, index):
if index <= 1:
return index
res = [1]
t2 = t3 = t5 = 0
for i in range(1, index):
# 每次新生成的丑数是由三个数字的最小值构成的
temp = min(res[t2] * 2, res[t3] * 3, res[t5] * 5)
res.append(temp)
# 如果其中一个序列这次被选中,下一次从这个队列生成出用来比较的丑数就在这一次队列向后移动一位
if temp == res[t2] * 2:
t2 += 1
if temp == res[t3] * 3:
t3 += 1
if temp == res[t5] * 5:
t5 += 1
return res[-1]
发表于 2019-05-11 21:13:48
回复(0)
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
class Solution { public://别人的代码就是精简，惭愧啊，继续学习。 int GetUglyNumber_Solution(int index) { if (index < 7)return index; vector<int> res(index); res[0] = 1; int t2 = 0, t3 = 0, t5 = 0, i; for (i = 1; i < index; ++i) { res[i] = min(res[t2] * 2, min(res[t3] * 3, res[t5] * 5)); if (res[i] == res[t2] * 2)t2++; if (res[i] == res[t3] * 3)t3++; if (res[i] == res[t5] * 5)t5++; } return res[index - 1]; } };