博客

Python：丑数

  • Post author:
  • Post category:python



牛客网上的剑指 offer的在线编程：

题目描述

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

res用来存放排好序的丑数。


每一个丑数 n 都是从小于 n 的丑数 乘以 2，3，5 中得来的。


2、所以每次只需要考虑 <= n的丑数中，没有加入res的值，例如为(n-1)*5，那么只需要比较(n-1)*5，n*2，n*3的值，取最小存入res

 
class Solution:
    def GetUglyNumber_Solution1(self, index):
        if index <= 0:
            return 0
        index2, index3, index5 = 0, 0, 0
        res = [1]
        while len(res) < index:
            temp = min(res[index2]*2, res[index3]*3, res[index5]*5)
            if not temp in res:
                res.append(temp)
            if temp % 2 == 0:
                index2 += 1
            if temp % 3 == 0:
                index3 += 1
            if temp % 5 == 0:
                index5 += 1
        return res[index - 1]

方法二思路：

1、每一个丑数 n 都是从小于 n 的丑数 乘以 2，3，5 中得来的。res用来存放排好序的丑数

2、取res中最大的丑数乘以 2，3，5 ，对得到的值先做个判断，把不在comp中的值存入comp，取comp的最小值，如果最小值不在res中，则存入res，

再在comp中删除这个最小值

3、循环步骤2，直到len(res)等于index
class Solution:
    def GetUglyNumber_Solution(self, index):
        # write code here
        if index <= 0:
            return 0
        elif index == 1:
            return 1
        else:
            comp = []
            res = [1]
            while len(res) < index:
                if not max(res)*2 in comp:
                    comp.append(max(res)*2)
                if not max(res)*3 in comp:
                    comp.append(max(res)*3)
                if not max(res)*5 in comp:
                    comp.append(max(res)*5)
                if not min(comp) in res:
                    res.append(min(comp))
                    comp.pop(comp.index(min(comp)))
            return res[index - 1]


版权声明：本文为Lynette_bb原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。