汇芳书院

专注计算机视觉、机器学习、分布式计算等领域, 兼聊投资、写作、生活

0%

丑数(系列)

发表于 更新于 分类于 Valine：
本文字数： 4.2k 阅读时长 ≈ 4 分钟

263. 丑数

丑数 就是只包含质因数 2、3 和 5 的正整数。

给你一个整数 n ，请你判断 n 是否为 丑数 。如果是，返回 true ；否则，返回 false 。

 

示例 1：

输入：n = 6
输出：true
解释：6 = 2 × 3
示例 2：

输入：n = 1
输出：true
解释：1 没有质因数，因此它的全部质因数是 {2, 3, 5} 的空集。习惯上将其视作第一个丑数。
示例 3：

输入：n = 14
输出：false
解释：14 不是丑数，因为它包含了另外一个质因数 7 。

分别对n反复除以质因子2,3,5, 如果最后剩余的值为1，则OK

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    bool isUgly(int n) {
        if (n <= 0) return false;
        if (n == 1) return true;
        int factors[3] = {2, 3, 5};
        for (auto factor : factors) {
            while (n % factor == 0) n = n/factor;
        }
        return n == 1;
    }
};

264. 丑数 II

给你一个整数 n ，请你找出并返回第 n 个 丑数 。

丑数 就是只包含质因数 2、3 和/或 5 的正整数。

 

示例 1：

输入：n = 10
输出：12
解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
示例 2：

输入：n = 1
输出：1
解释：1 通常被视为丑数。

暴力法

直接按自然数顺序遍历isUgly, 但是时间复杂度O(nlogn)太高，

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
class Solution {
public:
    int nthUglyNumber(int n) {
        if (n == 1) return 1;
        int count = 1;
        int i = 1;
        while (count < n) {
            i++;
            if (isUgly(i)) {
                count++;
            }
        }
        return i;
    }

    bool isUgly(int n) {
        if (n <= 0) return false;
        if (n == 1) return true;
        int factors[3] = {2, 3, 5};
        for (auto factor : factors) {
            while (n % factor == 0) n = n/factor;
        }
        return n == 1;
    }
};

小顶堆

每次从堆顶取出最小值，然后乘以三个因子后的数加入堆，为了避免重复，可以使用集合过滤。

时间复杂度也是O(nlogn), 但是确能通过OJ了

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
class Solution {
public:
    int nthUglyNumber(int n) {
        int factors[3] = {2, 3, 5};
        unordered_set<long> seen;
        // 默认大顶堆
        priority_queue<long, vector<long>, greater<long>> heap;
        long ans = 1;
        heap.push(ans);
        seen.insert(ans);
        long cur = 1;
        for(int i = 0; i < n; i++) {
            cur = heap.top();
            heap.pop();
            for (auto factor : factors) {
                long next = cur * factor;
                if (!seen.count(next)) {
                    seen.insert(next);
                    heap.push(next);
                }
            }
        }
        return cur;

        
    }
};

三个数组(或者叫动态规划)

dp[i] = min(dp[i-1]*2, dp[i-1]*3, dp[i-1]*5)
初始时候dp[1] = 1;
后面不断的乘以2，3，5分别可以得到3个数组，就是不知道下一次该选谁，所以有三个指针记录当前走到的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int nthUglyNumber(int n) {
        int factors[3] = {2, 3, 5};
        vector<int> dp(n+1);
        int p2 = 1, p3 = 1, p5 = 1;
        dp[1] = 1;
        int pre = 1, ans = 1;
        for (int i = 2; i <= n; i++) {
            int num2 = dp[p2]*2, num3 = dp[p3]*3, num5 = dp[p5]*5;
            dp[i] = min(num2, min(num3, num5));
            if (dp[i] == num2) p2++;
            if (dp[i] == num3) p3++;
            if (dp[i] == num5) p5++;
        }
        return dp[n];

        
    }
};

313. 超级丑数

超级丑数 是一个正整数，并满足其所有质因数都出现在质数数组 primes 中。

给你一个整数 n 和一个整数数组 primes ，返回第 n 个 超级丑数 。

题目数据保证第 n 个 超级丑数 在 32-bit 带符号整数范围内。

 

示例 1：

输入：n = 12, primes = [2,7,13,19]
输出：32
解释：给定长度为 4 的质数数组 primes = [2,7,13,19]，前 12 个超级丑数序列为：[1,2,4,7,8,13,14,16,19,26,28,32] 。
示例 2：

输入：n = 1, primes = [2,3,5]
输出：1
解释：1 不含质因数，因此它的所有质因数都在质数数组 primes = [2,3,5] 中。
 
提示：

1 <= n <= 105
1 <= primes.length <= 100
2 <= primes[i] <= 1000
题目数据 保证 primes[i] 是一个质数
primes 中的所有值都 互不相同 ，且按 递增顺序 排列

思路和普通丑数的处理方式一样

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        int prime_size = primes.size();
        vector<int> pointers(prime_size, 1); //指针列表
        vector<long> tmp_nums(prime_size, 1); //存储每次计算的临时结果
        vector<long> dp(n+1, INT_MAX);
        dp[1] = 1;
        for (int i = 2; i <=n; i++) {
            for (int p_index = 0; p_index < prime_size; p_index++) {
                tmp_nums[p_index] = primes[p_index]*dp[pointers[p_index]];
                if (tmp_nums[p_index] < dp[i]) dp[i] = tmp_nums[p_index];
                
            }
            for (int p_index = 0; p_index < prime_size; p_index++) {
                if (dp[i] == tmp_nums[p_index]) {
                    pointers[p_index]++;
                }
            }
        }
        return dp[n];
    }
};

1201. 丑数 III

给你四个整数：n 、a 、b 、c ，请你设计一个算法来找出第 n 个丑数。

丑数是可以被 a 或 b 或 c 整除的 正整数 。

 

示例 1：

输入：n = 3, a = 2, b = 3, c = 5
输出：4
解释：丑数序列为 2, 3, 4, 5, 6, 8, 9, 10… 其中第 3 个是 4。
示例 2：

输入：n = 4, a = 2, b = 3, c = 4
输出：6
解释：丑数序列为 2, 3, 4, 6, 8, 9, 10, 12… 其中第 4 个是 6。
示例 3：

输入：n = 5, a = 2, b = 11, c = 13
输出：10
解释：丑数序列为 2, 4, 6, 8, 10, 11, 12, 13… 其中第 5 个是 10。
示例 4：

输入：n = 1000000000, a = 2, b = 217983653, c = 336916467
输出：1999999984

这题和前面的题，似乎都不太一样，

递推的思路，时间复杂度太高

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
class Solution {
public:
    int nthUglyNumber(int n, int a, int b, int c) {
        int factors[3] = {a, b, c};
        vector<int> dp(n+2, INT_MAX);
        int p2 = 1, p3 = 1, p5 = 1;
        dp[1] = 1;
        int pre = 1, ans = 1;
        for (int i = 2; i <= n+1; i++) {
            // 这一行的计算和以前不一样
            int num2 = p2*factors[0], num3 = p3*factors[1], num5 = p5*factors[2];
            // cout << "p2,p3,p5: " << p2 << " " << p3 << " " << p5 << endl;
            // cout << "num2,num3,num5: " << num2 << "," << num3 << ',' << num5;

            dp[i] = min(num2, min(num3, num5));
            if (dp[i] == num2) p2++;
            if (dp[i] == num3) p3++;
            if (dp[i] == num5) p5++;
            cout << " " << dp[i];
        }
        return dp[n+1];

        
    }
    
};

二分

TODO

坚持原创分享，您的支持将鼓励我继续创作

欢迎关注我的其它发布渠道

------------- 本文结束,感谢阅读 如有问题可留言交流 -------------