题目描述
把只包含质因子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/SysuJayceclass 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()