剑指49：丑数

传送门

nowcoder
leetcode

题目描述

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

C++ 代码 - nowcoder

/*
    根据丑数的定义，丑数应该是另一个丑数乘以 2、3、5 的结果。
    因此，创建一个数组保存排好序的丑数，每个丑数由前面的丑数乘以 2、3、5 得到。

    状态表示：
        f[i] 表示第 i 个丑数，第 n 个丑数为 f[n]
    状态计算：
        如何得到其余的丑数？定义三个指针 p2, p3, p5 表示下一个丑数是当前丑数乘以相应的质因数。
        当 2 <= i <= n 时，令 f[i] = min(f[p2] * 2, f[p3] * 3, f[p5] * 5)，然后比较 f[i] 和 f[p2], f[p3], f[p5] 是否相等，若相等则对应的指针加 1。
    初始化：
        f[0] = 1
        p2 = 1, p3 = 1, p5 = 1
    
    时间复杂度：O(n)
        需要计算数组中的 n 个元素，每个元素的计算可以在 O(1) 时间内完成
    空间复杂度：O(n)
*/
class Solution {
public:
    int GetUglyNumber_Solution(int index) {
        if (index <= 6) return index;

        vector<int> f(index + 1, 0);
        f[1] = 1;
        int i2 = 1, i3 = 1, i5 = 1;
        for (int i = 2; i <= index; i ++) {
            int minNum = min(min(f[i2] * 2, f[i3] * 3), f[i5] * 5);
            if (minNum == f[i2] * 2) i2 ++;
            if (minNum == f[i3] * 3) i3 ++;
            if (minNum == f[i5] * 5) i5 ++;
            f[i] = minNum;
        }

        return f[index];
    }
};

C++ 代码 - leetcode

/*
    状态表示：
        f[i] 表示第 i 个丑数，第 n 个丑数为 f[n]
    状态计算：
        如何得到其余的丑数？定义三个指针 p2, p3, p5 表示下一个丑数是当前丑数乘以相应的质因数。
        当 2 <= i <= n 时，令 f[i] = min(f[p2] * 2, f[p3] * 3, f[p5] * 5)，然后比较 f[i] 和 f[p2], f[p3], f[p5] 是否相等，若相等则对应的指针加 1。
    
    时间复杂度：O(n)
    空间复杂度：O(n)
*/
class Solution {
public:
    int nthUglyNumber(int n) {
        if (n <= 6) return n;

        vector<int> f(n + 1); // 最终合并的有序链表（结果链表）
        f[1] = 1;
        int p2 = 1, p3 = 1, p5 = 1; // 三个有序链表的头节点的值
        // 合并三个有序链表
        for (int i = 2; i <= n; i ++) {
            int minVal = min(min(f[p2] * 2, f[p3] * 3), f[p5] * 5); // 取三个链表的最小结点
            f[i] = minVal; // 连接到结果链表
            if (f[i] == f[p2] * 2) p2 ++;
            if (f[i] == f[p3] * 3) p3 ++;
            if (f[i] == f[p5] * 5) p5 ++;
        }

        return f[n]; // 返回第 n 个丑数
    }
};