使用Python找丑数

一个正整数的因数只有1、2、3、5和它本身，那么这个数就是丑数。那么丑数从小到大的序列为 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, … . 规定，1为最小的丑数。

问题：给出一个正整数n，找到第n个丑数。

方法一：
遍历所有正整数，判断其是否为丑数；
当丑数计数器count等于n时停止。

# Python3 code to find nth ugly number

# This function divides a by greatest
# divisible power of b
def maxDivide(a,b):
    while a % b ==0:
        a = a /b
    return a

# Function to check if a number
# is ugly or not
def isUgly( no ):
    no = maxDivide(no,5)
    no = maxDivide(no,3)
    no = maxDivide(no,2)
    if no ==1:
        return 1
    return 0
    #return 1 if no==1 else 0

# Function to get the nth ugly number
def getNthUglyNo(n):
    i = 1
    count =1  #ugly number count

    #Check for all integers untill
    #ugly count becomes n
    while n > count:
        i += 1
        if isUgly(i):
            count +=1
    return i

#Drive code to test above functions
no = getNthUglyNo(9)
print('%d%s%d'%(no,'th ugly no. is ',no))

这种方法的时间复杂度比较高，因为需要遍历所有的正整数（在找到目标丑数之前）；但是它的空间复杂度为O(1)；

方法二：
丑数序列为 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, …
因为丑数都是2，3，5的倍数，因此我们可以把丑数序列分成三组：
(1) 1×2, 2×2, 3×2, 4×2, 5×2, …
(2) 1×3, 2×3, 3×3, 4×3, 5×3, …
(3) 1×5, 2×5, 3×5, 4×5, 5×5, …
我们观察到，三组数据其实是丑数序列ugly[]和2，3，5的乘积，即：
(1)ugly[] * 2
(2)ugly[] * 3
(3)ugly[] * 5
因此我们可以使用类似合并的方法将三个数组由小到大排列成一数组。

# python program to find the nth ugly number

#查找第n个丑数的函数
def getNthUglyNo(n):
    ugly = [0] * n    #1、定一个数组按从小到大，存放丑数
    ugly[0] = 1       #2、初始化最小的丑数为1


    i2 = i3 = i5 = 0  #3、定义三个索引指向丑数序列的不同位置，分别作为2，3，5的乘数
                      #构建三个序列，三个索引的前进速率不一样，i2最快，i5最慢

    next_multiple_of_2 = 2 * ugly[0]    #初始化三个序列的首位
    next_multiple_of_3 = 3 * ugly[0]
    next_multiple_of_5 = 5 * ugly[0]

    for l in range(1, n):
        # 每次选取三个序列中最小的数，放进丑数数组中
        ugly[l] = min(next_multiple_of_2, next_multiple_of_3, next_multiple_of_5)   
        
        #三个序列以此递增
        if ugly[l] == next_multiple_of_2:
            i2 += 1
            next_multiple_of_2 = ugly[i2] * 2
        if ugly[l] == next_multiple_of_3:
            i3 += 1
            next_multiple_of_3 = ugly[i3] * 3
        if ugly[l] == next_multiple_of_5:
            i5 += 1
            next_multiple_of_5 = ugly[i5] * 5

    return ugly[n - 1]  #返回丑数数组中的第n位丑数

def main():
    n = 150

    print getNthUglyNo(n)

if __name__ == '__main__':
    main()

Time Complexity: O(n)
Auxiliary Space: O(n)

最后

以上就是轻松纸鹤为你收集整理的使用Python找丑数的全部内容，希望文章能够帮你解决使用Python找丑数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。