剑指offer 面试题49. 丑数（中）& LeetCode 264. 丑数 II（中）

这道题的关键是利用之前的丑数去生成之后的丑数，想清楚这个关系很重要。

Question

我们把只包含因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

示例: 

1
2
3
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
说明: 1 是丑数（PS：《剑指offer》上1也被认为是一个丑数）；n 不超过1690。

测试用例

功能测试（输入2、3、4、5、6等）。 特殊输入测试（边界值1；无效输入0）。 性能测试（输入较大的数字，如1500）。

本题考点

考查应聘者对时间复杂度的理解。绝大部分应聘者都能想出第一种思路。在面试官提示还有更快的解法之后，应聘者能否分析出时间效率的瓶颈，并找出解决方案，是能否通过这轮面试的关键。 考查应聘者的学习能力和沟通能力。丑数对很多人而言是一个新概念。有些面试官喜欢在面试的时候定义一个新概念，然后针对这个新概念出面试题。这就要求应聘者听到不熟悉的概念之后，要有主动积极的态度，大胆向面试官提问，经过几次思考、提问、再思考的循环，在短时间内理解这个新概念。这个过程就体现了应聘者的学习能力和沟通能力。

Intuition

逐个判断

从2开始，逐个判断当前数字是否是丑数，如果是就将变量 uglyCount 加1。直到 uglyCount 等于 n。

动态规划

状态定义：设动态规划数组 dp， dp[i] 为第 i+1 个丑数。 转移方程：当索引 a、b、c 满足以下条件时，dp[i] 为三种情况的最小值； 每轮计算 d1p[i] 后，需要更新索引 a, b, c 的值，使其始终满足方程条件。实现方法：分别独立判断 dp[i] 和 dp[a]×2 , dp[b]×3 , dp[c]×5 的大小关系，若相等则将对应索引 a , b , c 加 1 。

1
2
3
4
dp[a] × 2 > dp[i-1] >= dp[a-1] × 2
dp[b] × 3 > dp[i-1] >= dp[b-1] × 2
dp[c] × 5 > dp[i-1] >= dp[c-1] × 2
dp[i] = min(dp[a] × 2, dp[b] × 3, dp[c] × 5)

初始状态：dp[0]=1，即第一个丑数为1； 返回值：dp[n-1]，即返回的第n个丑数 复杂度分析： 时间复杂度 \(O(N)\) ： 其中 \(N = n\) ，动态规划需遍历计算 dp 列表。 空间复杂度 \(O(N)\) ： 长度为 \(N\) 的 dp 列表使用 \(O(N)\) 的额外空间。

参考连接： 作者：Krahets 链接：https://leetcode-cn.com/problems/chou-shu-lcof/solution/mian-shi-ti-49-chou-shu-dong-tai-gui-hua-qing-xi-t/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Code

  • 逐个判断
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution:
    def isUgly(self, num: int) -> bool:
        if num < 1: return False
        divisors = [2, 3, 5]
        while True:
            if num == 1.0:
                return True
            is_ugly = False
            for divisor in divisors:
                if num % divisor == 0:
                    num /= divisor
                    is_ugly = True
                    break
            if not is_ugly:
                break
        return False

    def nthUglyNumber(self, n: int) -> int:
        """逐个判断
        """
        index = n
        if index < 1:
            return 0
        number = 0
        uglyFound = 0
        while uglyFound < index:
            number += 1
            if self.isUgly(number):
                uglyFound += 1
        return number

这种方法会超时，时间复杂度为 \(O(N \times k)\)，\(N\) 为第 \(n\) 个丑数值，\(k\) 为 isUgly 函数中循环次数的平均值。

  • 动态规划
1
2
3
4
5
6
7
8
9
10
class Solution:
    def nthUglyNumber(self, n: int) -> int:
        dp, a, b, c = [1] * n, 0, 0, 0
        for i in range(1, n):
            n2, n3, n5 = dp[a] * 2, dp[b] * 3, dp[c] * 5 
            dp[i] = min(n2, n3, n5)
            if dp[i] == n2: a += 1
            if dp[i] == n3: b += 1
            if dp[i] == n5: c += 1
        return dp[-1]

Related Question

LeetCode 263. 丑数（易）

Question

编写一个程序判断给定的数是否为丑数，丑数就是只包含质因数 2, 3, 5 的正整数。

示例 1: 

1
2
3
输入: 6
输出: true
解释: 6 = 2 × 3
示例 2: 
1
2
3
输入: 8
输出: true
解释: 8 = 2 × 2 × 2
示例 3: 
1
2
输入: 14
输出: false
解释: 14 不是丑数，因为它包含了另外一个质因数 7。 说明：1 是丑数，输入不会超过 32 位有符号整数的范围: [\(−2^{31}\), \(2^{31} − 1\)]。

Intuition

所谓一个数 \(m\) 是另一个数 \(n\) 的因子，是指 \(n\) 能被 \(m\) 整除，也就是 \(n \% m = 0\)。根据丑数的定义，丑数只能被2、3和5整除。也就是说，如果一个数拥有2、3、5之外的因数，那这个数就不是丑数了。

Code

  • 简单版本
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def isUgly(self, num: int) -> bool:
        if num < 1: return False
        while True:
            if num == 1.0:
                return True
            if num % 2 == 0:
                num /= 2
            elif num % 3 == 0:
                num /= 3
            elif num % 5 == 0:
                num /= 5
            else:
                break

        return False
  • 可扩展版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution:
    def isUgly(self, num: int) -> bool:
        if num < 1: return False
        divisors = [2, 3, 5]
        while True:
            if num == 1.0:
                return True
            is_ugly = False
            for divisor in divisors:
                if num % divisor == 0:
                    num /= divisor
                    is_ugly = True
                    break
            if not is_ugly:
                break
        return False

class TestSolution(unittest.TestCase):
    def setUp(self):
        self.test_class = Solution()

    def test_solution(self):
        # 功能测试
        inputs = [6, 8, 14]
        # 边界值的测试
        # inputs += []
        # 特殊样例
        inputs += [-1]
        # 输出的答案
        answers = [True, True, False, False]
        res = []
        for i in range(len(inputs)):
            res.append(self.test_class.isUgly(inputs[i]))
        self.assertEqual(res, answers)
 
    def tearDown(self):
        del self.test_class


if __name__ == "__main__":
    unittest.main()