题目描述:把只包含质因子 2、3 和 5 的数称作丑数(Ugly Number)。例如 6、8 都是丑数,但 14 不是,因为它包含质因子 7。习惯上我们把 1 当做是第一个丑数。求按从小到大的顺序的第 N 个丑数。

Solutions

首先我们肯定要确定一个判断是丑数的函数,然后我们按照顺序判断每个整数是不是丑数:

# -*- coding:utf-8 -*-
class Solution:
    def IsUglyNumber(self, number):
        while number % 2 == 0:
            number //= 2
        while number % 3 == 0:
            number //= 3
        while number % 5 == 0:
            number //= 5
        return True if number == 1 else False
    
    def GetUglyNumber_Solution(self, index):
        # write code here
        if index <= 0:
            return 0
        count = 0
        number = 0
        while count < index:
            number += 1
            if self.IsUglyNumber(number):
                count += 1
        return number

这种解法牛客网平台都过不了,可见时间效率较低,而且其中有较多的求余和除法运算,势必是不合格的解法。

一种做法是以空间换时间,我们可以在原来的丑数基础上乘以 2、3、5,但是注意得控制存储的丑数顺序,具体可见书本 183 页。

# -*- coding:utf-8 -*-
class Solution:
    def GetUglyNumber_Solution(self, index):
        # write code here
        if index <= 0:
            return 0
        next_index = 1
        res = [1]
        t2 = t3 = t5 =0
        while next_index < index:
            min_val = min(res[t2] * 2, res[t3] * 3, res[t5] * 5)
            res.append(min_val)
            while res[t2] * 2 <= min_val:
                t2 += 1
            while res[t3] * 3 <= min_val:
                t3 += 1
            while res[t5] * 5 <= min_val:
                t5 += 1
            next_index += 1
        return res[-1]

References

  1. 034. 丑数