查找第n个丑数

老夏

       查找第n个丑数

    丑数指的是只包含质因子2、3和5的数。例如6、8都是丑数，但7、14不是，因为它们包含质因子7。习惯上将1当做是第一个丑数，前20个丑数分别为：1、2、3、4、5、6、8、9、10、12、15、16、18、20、24、25、27、30、32、36。
    解此题，首先需要给三个质因子2、3和5分别设定一个默认的索引0；然后用第一个丑数1分别乘以质因子2、3和5，并取出相乘后最小的数，这个数就是第2个丑数，之后将该数对应的质因子的索引加1，以便于获取下一个丑数；最后，按照此算法，不断进行循环，即可获得按照升序排列的丑数，然后返回指定索引的丑数即可完成题目要求。
    解析代码如下：

1. def GetUglyNumber(index):
   
2.     # 如果索引小于1，则返回None
   
3.     if index < 1:
   
4.         return None
   
5.     # 将第一个丑数1，放入列表中，该列表用于存放按照升序排序的所有丑数
   
6.     uglyList = [1]
   
7.     # 将质因子2、3、5的默认索引设为0
   
8.     twoPointer = 0
   
9.     threePointer = 0
   
10.     fivePointer = 0
    
11.     # 设定默认索引
    
12.     count = 1
    
13.     # 如果当前索引与要查找的索引相等，则返回该索引对应的丑数即可
    
14.     while count != index:
    
15.         # 将最小的丑数存入列表中
    
16.         minValue = min(2 * uglyList[twoPointer], 3 * uglyList[threePointer], 5 * uglyList[fivePointer])
    
17.         uglyList.append(minValue)
    
18.         count += 1
    
19.         # 如果当前丑数含有质因子2，则其索引加1
    
20.         if minValue == 2 * uglyList[twoPointer]:
    
21.             twoPointer += 1
    
22.         # 如果当前丑数含有质因子3，则其索引加1
    
23.         if minValue == 3 * uglyList[threePointer]:
    
24.             threePointer += 1
    
25.         # 如果当前丑数含有质因子5，则其索引加1
    
26.         if minValue == 5 * uglyList[fivePointer]:
    
27.             fivePointer += 1
    
28.     # 返回要查找的丑数
    
29.     return uglyList[count - 1]
    
30. # 查找第8个丑数
    
31. ret = GetUglyNumber(8)
    
32. print(ret)

复制代码