丑数
设计一个算法，找出只含素因子2，3，5 的第 n 小的数。
符合条件的数如：1, 2, 3, 4, 5, 6, 8, 9, 10, 12...
样例
如果n = 9， 返回 10
挑战
要求时间复杂度为O(nlogn)或者O(n)
注意事项
我们可以认为1也是一个丑数
丑数概念:
百度百科只包含因子2,3,5的正整数被称作丑数
思路:
1.遍历
使用遍历法求第k个丑数，从1开始遍历，如果是丑数则count++，直到count=k为止。那么如何判断丑数呢？根据丑数的定义，丑数只有2，3，5这三个因子，那么我们就拿数字除以这三个因子。具体算法如下:
Step1.如果一个数能够被2整除，那么让他继续除以2；
Step2.如果一个数能够被3整除，那么让他继续除以3；
Step3.如果一个数能够被5整除，那么让他继续除以5；
Step4.如果最后这个数变为1，那么这个数就是丑数，否则不是。
class Solution:
"""
@param n: An integer
@return: the nth prime number as description.
"""
def isUglNumber(self,number):
while number % 2 == 0 :
number = number // 2
while number % 5 == 0 :
number = number // 5
while number % 3 == 0 :
number = number //3
if number == 1:
return True
else:
return False
def nthUglyNumber(self, n):
if n <= 0:
return 0
number = 0
uglNumber = 0
while uglNumber < n :
number += 1
if self.isUglNumber(number):
uglNumber += 1
return number
这种方法,因为所有的整数都要计算一次,即使不是丑数也要计算,时间效率不高.
2.空间换算时间方法
根据丑数的定义，我们可以知道丑数可以由另外一个丑数乘以2，3或者5得到。因此我们可以创建一个数组，里面的数字是排好序的丑数，每一个丑数都是前面的丑数乘以2，3或者5得到的。
我们把得到的第一个丑数乘以2以后得到的大于M的结果记为M2。同样，我们把已有的每一个丑数乘以3和5，能得到第一个大于M的结果M3和M5。那么M后面的那一个丑数应该是M2,M3和M5当中的最小值：Min(M2,M3,M5)。比如将丑数数组中的数字按从小到大乘以2，直到得到第一个大于M的数为止，那么应该是2*2=4M，所以M2=6。同理，M3=6，M5=10。所以下一个丑数应该是6。
前面分析的时候，提到把已有的每个丑数分别都乘以2，3和5。事实上这不是必须的，因为已有的丑数是按顺序存放在数组中的，对乘以2而言，肯定存在某一个丑数T2，排在她之前的每一个丑数乘以2得到的结果都会小于等于(<=)已有最大的丑数，在它之后的每一个丑数乘以2得到的结果都会大于已有的最大丑数。因此我们只需要记下这个丑数的位置，同时每次生成新的丑数的时候去更新这个T2。对于乘以3和5，同样存在这样的T3和T5。
代码示例:
def nthUglyNumber(self, n):
if n <= 0:
return 0
uglNumList = [1]
p1, p2, p3 = 0, 0, 0
while len(uglNumList) < n:
v2 = uglNumList[p1] * 2
v3 = uglNumList[p2] * 3
v5 = uglNumList[p3] * 5
minV = min(v2, v3, v5)
if v2 == minV:
p1 += 1
if v3 == minV:
p2 += 1
if v5 == minV:
p3 += 1
uglNumList.append(minV)
return uglNumList[-1]
网
