微信公众号：路人zhang
扫码关注微信公众号

回复“面试手册”，获取本站PDF版

回复“简历”，获取高质量简历模板

回复“加群”，加入程序员交流群

回复“电子书”，获取程序员类电子书

当前位置： 算法 > 剑指offer > 剑指offer 49.丑数

剑指offer 49.丑数

题目描述

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

示例:

输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

说明:   

  1. 1 是丑数。
  2. n  不超过 1690。

算法

(三路归并) O(n)

使用 vector<int> res 存储每个丑数，且已知第一个丑数是 1，即 res[0] = 1。

用 i, j, k 三个指针分别指向三个序列，i 指向质因子包含 2 的所有数组成的序列 II，j 指向质因子包含 3 的所有数组成的序列 III，k 指向质因子包含 5 的所有数组成的序列 V。初始状态下三个指针都是 0，指向第一个丑数 res[0] = 1。

三路归并，每次取 res[i] * 2, res[j] * 3, res[k] * 5 中的最小值，就是下一个丑数。 其中 res[i] 是序列 II 的第 i 个数，那么 res[i] * 2 就是第 i + 1 个数，res[j] 是序列 III 的第 j 个数，那么 res[j] * 3 就是第 j + 1 个数，res[k] 是序列 V 的第 k 个数，那么 res[k] * 5 就是第 k + 1 个数 res[0] = 1 不属于任何序列。

如果下一个丑数为 res[i] * 2，则 i 指针向往后移，如果 res[j] * 3，则 j 指针往后移，如果 res[k] * 5，则 k 指针往后移，如果下一个丑数即是 2 的倍数也是 3 的倍数，那么指针 i 和 j 都要往后移

代码实现方式上是直接在 res 数组中边扩展序列边计算丑数。

时间复杂度

求第 n 个丑数，已知第一个丑数是 1，循环 n – 1 次即可求得，时间复杂度为 O(n)。

空间复杂度

O(n)

C++ 代码

class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> res(1, 1); // 第一个丑数是 1
        int i = 0, j = 0, k = 0;
        while ( -- n) {
            int t = min(res[i] * 2, min(res[j] * 3, res[k] * 5));
            res.push_back(t);

            if (res[i] * 2 == t) i ++ ;
            if (res[j] * 3 == t) j ++ ;
            if (res[k] * 5 == t) k ++ ;
        }
        return res.back();
    }
};

Java 代码

class Solution {
    public int nthUglyNumber(int n) {
        List<Integer> res = new ArrayList<>();
        res.add(1); // 第一个丑数是 1
        int i = 0, j = 0, k = 0;
        while ( -- n > 0) {
            int t = Math.min(res.get(i) * 2, Math.min(res.get(j) * 3, res.get(k) * 5));
            res.add(t);

            if (res.get(i) * 2 == t) i ++ ;
            if (res.get(j) * 3 == t) j ++ ;
            if (res.get(k) * 5 == t) k ++ ;
        }
        return res.get(res.size() - 1);
    }
}

Python 代码

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        res = [1]  # 第一个丑数是 1
        i, j, k = 0, 0, 0
        while n > 1:
            t = min(res[i] * 2, min(res[j] * 3, res[k] * 5))
            res.append(t)

            if res[i] * 2 == t:
                i += 1
            if res[j] * 3 == t:
                j += 1
            if res[k] * 5 == t:
                k += 1

            n -= 1

        return res[-1]

本文由读者提供，Github地址：https://github.com/tonngw

点击面试手册，获取本站面试手册PDF完整版

剑指offer