Sui Xin's Blog

[剑指Offer]丑数

Posted on In Disqus:

题目描述

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

解题思路

  1. 方法一：从1开始逐个判断每个整数是否为丑数，直到找到N个丑数为止。根据丑数定义，其只能被2， 3和5整数，所以一直除，判断最后是否为1；
  2. 方法二：丑数有生成的规则，除1之外，每个丑数均是由某个丑数乘以2，3或5得来的，所以可以将每次添加到丑数列表的数分别乘以2，3和5添加到另一个列表中，每次取第二个列表最小的元素；
  3. 方法三：维护三个指针，分别指向丑数列表待乘2，3和5的数字位置，每次添加每个指针处数字乘以对应2，3和5的最小值，并随后判断哪个指针需向前移动一位。

代码

Python(2.7.3)

方法一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# -*- coding:utf-8 -*-
class Solution:
    def GetUglyNumber_Solution(self, index):
        # write code here
        num = 0
        cur = 0
        while cur < index:
            num += 1
            while not self.isUglyNumber(num):
                num += 1
            cur += 1
        return num
    
    def isUglyNumber(self, num):
        while num % 2 == 0:
            num /= 2
        while num % 3 == 0:
            num /= 3
        while num % 5 == 0:
            num /= 5
        return num == 1

方法二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# -*- coding:utf-8 -*-
class Solution:
    def GetUglyNumber_Solution(self, index):
        # write code here
        if index < 1:
            return 0
        ugly = []
        tmp = {1}
        count = 0
        while count < index:
            min_ugly = min(tmp)
            ugly.append(min_ugly)
            tmp.remove(min_ugly)
            tmp.add(2 * min_ugly)
            tmp.add(3 * min_ugly)
            tmp.add(5 * min_ugly)
            count += 1
        return ugly[-1]

运行时间：35ms
占用内存：5740k

方法三

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# -*- coding:utf-8 -*-
class Solution:
    def GetUglyNumber_Solution(self, index):
        # write code here
        if index < 1:
            return 0
        ugly = [1]
        p2, p3, p5 = 0, 0, 0
        for _ in range(index - 1):
            new_ugly = min(ugly[p2] * 2, ugly[p3] * 3, ugly[p5] * 5)
            ugly.append(new_ugly)
            if new_ugly % 2 == 0:  # 也可改为判断ugly[p2] * 2 == new_ugly
                p2 += 1
            if new_ugly % 3 == 0:
                p3 += 1
            if new_ugly % 5 == 0:
                p5 += 1
        return ugly[-1]

运行时间：36ms
占用内存：5708k