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

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

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

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

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

当前位置: 算法 > 剑指offer > 剑指offer 49.丑数
本文链接:https://www.mianshi.online/2769.html

题目描述

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

示例:

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

说明:   

  1. 1 是丑数。
  2. 不超过 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完整版