本文主要是介绍*[剑指offer] 丑数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目内容
https://www.nowcoder.com/practice/6aa9e04fc3794f68acf8778237ba065b?tpId=13&tqId=11186&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
把只包含质因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
题目思路
这道题目考虑使用多个指针来进行计算。对于一个丑数序列[1,2,3,4,5,6,8,9....]来说,后边的任何一个数字都是前面的某一个数字*2,3,5得到的。也就是说,我们要找到前面的那个数字即可。所以才用了多指针的方法,如果这个数字乘以2,3或者5采用了,那么再之后的数字就不会是这个数字乘以2,3或者5,所以2,3,5的指针就要滑动到下一个位置上。
程序代码
# -*- coding:utf-8 -*-
class Solution:def GetUglyNumber_Solution(self, index):# write code hereif index<1:return Falseif index==1:return 1res=[1]t2,t3,t5=0,0,0next_num=1while next_num<index:tmp=min(2*res[t2],3*res[t3],5*res[t5])res.append(tmp)if res[t2]*2<=tmp:t2+=1if res[t3]*3<=tmp:t3+=1if res[t5]*5<=tmp:t5+=1next_num+=1return res[next_num-1]
这篇关于*[剑指offer] 丑数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!