剑指offer 面试49题

面试49题：

题：丑数

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

解题代码一：时间效率不高，对每一个数都需要判断它是不是丑数（需要执行求余和除法操作）

# -*- coding:utf-8 -*-

class Solution:

    def GetUglyNumber_Solution(self, index):

        # write code here

        if index<=0:

            return 0

        number=0

        uglyFound=0

        while (uglyFound<index):

            number+=1

            if self.IsUgly(number):

                uglyFound+=1

        return number

    def IsUgly(self,number):

        while number%2==0:

            number=number//2

        while number%3==0:

            number=number//3

        while number%5==0:

            number=number//5

        return True if number==1 else False

解题代码二：推荐！“以空间换时间”

# -*- coding:utf-8 -*-

class Solution:

    def GetUglyNumber_Solution(self,index):

        if index<=0:

            return 0

        res=[1]

        nextIndex=1

        t2=t3=t5=0

        while nextIndex<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

            nextIndex+=1

        return res[index-1]

巴特西

剑指offer 面试49题

最新文章

热门文章