题目描述
把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
公司主营业务：成都网站制作、成都网站建设、
外贸营销网站建设、移动网站开发等业务。帮助企业客户真正实现互联网宣传，提高企业的竞争能力。
成都创新互联是一支青春激扬、勤奋敬业、活力青春激扬、勤奋敬业、活力澎湃、和谐高效的团队。公司秉承以“开放、自由、严谨、自律”为核心的企业文化，感谢他们对我们的高要求，感谢他们从不同领域给我们带来的挑战，让我们激情的团队有机会用头脑与智慧不断的给客户带来惊喜。
成都创新互联推出
两当免费做网站回馈大家。
# -*- coding: utf-8 -*-
# @Time : 2019-07-11 23:24
# @Author : Jayce Wong
# @ProjectName : job
# @FileName : getUglyNumber.py
# @Blog : https://blog.51cto.com/jayce1111
# @Github : https://github.com/SysuJayce
class Solution:
"""
题目中丑数的定义是只包含因子2,3,5的数，特别地，1是第一个丑数。
解法1：
从1开始，逐个判断每个数字是不是丑数，如果是，则计数器加一，直到找到所要求的第n个丑数为止。
但是这样做的话会对很多非丑数进行计算，时间复杂度太高。
解法2：
定义一个数组，用于按顺序保存已经找到的丑数，再定义三个指针p2, p3, p5，其中p2指向数组中第一个
乘以2之后会比当前数组中末尾元素要大的数字；p3和p5同理。这样，当p2 * 2之后就会比当前最后一个
丑数要大，而当p3 * 3 之后也会比最后一个丑数要大， p5同理。这样，当前最后一个丑数之后的第一个
丑数就出现在p2 * 2, p3 * 3, p5 * 5之间，我们只需要比较这三个数的大小即可找到下一个丑数。
注意每找到一个这样的丑数之后我们就要更新p2, p3, p5，直到我们找到足够多的丑数。
这种方法是以空间换时间，我们维护了一个长度为n的数组，并最终返回这个数组的末尾元素。
"""
def GetUglyNumber_Solution(self, index):
if index <= 0:
return 0
uglyNumbers = [1] * index # 用于保存已找到丑数的数组
p2 = p3 = p5 = 0
idx = 1
while idx < index:
# 每次都这三个数中找一个最小的作为下一个丑数
nextUglyNumber = min(uglyNumbers[p2] * 2,
uglyNumbers[p3] * 3,
uglyNumbers[p5] * 5)
uglyNumbers[idx] = nextUglyNumber
# 然后更新这三个指针
while uglyNumbers[p2] * 2 <= nextUglyNumber:
p2 += 1
while uglyNumbers[p3] * 3 <= nextUglyNumber:
p3 += 1
while uglyNumbers[p5] * 5 <= nextUglyNumber:
p5 += 1
idx += 1
return uglyNumbers[index - 1]
def main():
solution = Solution()
index = 1
print(solution.GetUglyNumber_Solution(index))
if __name__ == '__main__':
main()
另外有需要云服务器可以了解下创新互联cdcxhl.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
文章标题：剑指offer：丑数-创新互联
网页网址：
http://cdkjz.cn/article/diegec.html
