题解 | #丑数#

# way 1 复杂度过高
class Solution:
    def GetUglyNumber_Solution(self, index):
        # write code here
        if index < 1:
            return None
        if index == 1:
            return index
        num = 2
        index = index - 1
        numcount = 0
        final = [1]
        while index:
            print("------\nindex:\t", index)
            count = num
            print("count:\t", count)
            while ((count % 2 == 0) or (count % 3 == 0) or (count % 5 == 0)) and (count != 0):
                if count % 2 == 0:
                    count = count // 2
                if count % 3 == 0:
                    count = count // 3
                if count % 5 == 0:
                    count = count // 5
            if count == 1:
                index = index - 1
                final.append(num)
                num = num + 1
            else:
                num = num + 1
            numcount += 1
            print("numcount:\t", numcount)
        return num - 1, final

# way 2 复杂度过高
class Solution:
    def GetUglyNumber_Solution(self, index):
        # write code here
        if index < 1:
            return None
        if index == 1:
            return 1
        count = 1

        def isUglyNumber(count):
            while count % 2 == 0:
                count = count // 2
            while count % 3 == 0:
                count = count // 3
            while count % 5 == 0:
                count = count // 5
            if count == 1:
                return True
            else:
                return False

        num = 2
        while True:
            if isUglyNumber(num):
                count += 1
            if count == index:
                return num
            num += 1

# way 3
class Solution:
    def GetUglyNumber_Solution(self, index):
        # write code here
        if index < 1:
            return 0
        uglylist = [1]
        twoPointer = 0
        threePointer = 0
        fivePointer = 0
        count = 1
        while count != index:
            minvalue = min(2*uglylist[twoPointer], 3*uglylist[threePointer], 5*uglylist[fivePointer])
            uglylist.append(minvalue)
            count += 1
            if minvalue == 2*uglylist[twoPointer]:
                twoPointer += 1
            if minvalue == 3*uglylist[threePointer]:
                threePointer += 1
            if minvalue == 5*uglylist[fivePointer]:
                fivePointer += 1

        return uglylist[count - 1]