剑指offer(C++)-JZ49:丑数(算法-其他)

2023-12-13 04:12:09

作者:翟天保Steven
版权声明:著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处

题目描述:

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

数据范围:0≤n≤2000

要求:空间复杂度 O(n)?, 时间复杂度 O(n)

示例:

输入:

7

返回值:

8

解题思路:

本题考察算法思维。两种解题思路:

1)优先队列-最小堆

? ? ? ?丑数是含质因子2、3、5的数,从1开始,1乘这三个因数得到的数就是丑数,以此类推,丑数乘因数也是丑数。考虑到这样操作可能会有重复,所以借助map完成去重。再构建优先队列-小顶堆往里面塞入丑数,放入的过程会自动进行排序,排序复杂度在O(log2n)。

? ? ? ?假设获取前n个丑数,就进行n次循环,每次循环将最小的丑数弹出,并放入新的丑数,放入的时候还需要进行重复性判断。

? ? ? ?综合下来,算法时间复杂度为O(nlog2n)。

2)动态规划

? ? ? ?丑数1 2 3 4 5 6 8 9 10等等,每个丑数一定是前面某个数的235倍数,可结合动态规划思想,设置三个步进下标ijk,将已知丑数依次乘235得到后续丑数,在此过程中还需要确保丑数是从小到大放入容器的,即进行最小值比较。

? ? ? ?为了直观些,简单模拟下前面几步的流程:

1)开始ijk均为0,则从数字1开始,丑数后续依次为2 3 5,其中2最小,则i升为1。

2)i为1,即第二个丑数2,用2的2倍也就是4和3 5比较,此时3最小,则j升为1。

3)i和j为1,即用第二个丑数2的2倍3倍,即4和6,和5比较,此时4最小,则i继续升为2。

4)i为2,j为1,k为0,用3的2倍、2的3倍、1的5倍比较,即6 6 4,此时5最小,则k升为1。

5)i为2,j为1,k为1,用3的2倍、2的3倍,2的5倍比较,即6 6 10,此时6最小,i和j同时升1。

? ? ? ?从上述5步可看到全局规律,ijk是从前往后慢慢推进的,结合了动态规划的思想,后续步进以前面为基准,动态扩展后续丑数

? ? ? ?该算法时间复杂度为O(n),也是题目理想解法。

测试代码:

1)优先队列-最小堆

#include <queue>
class Solution {
public:
    // 获取丑数
    int GetUglyNumber_Solution(int index) {
        // 判空
        if(index == 0){
            return 0;
        }
        // 定义因数集合
        vector<int> factors = { 2, 3, 5};
        // 定义哈希表
        unordered_map<long, bool> um;
        // 定义优选队列-小顶堆
        priority_queue<long, vector<long>, greater<>> pq;
        // 放入1
        um[long(1)] = true;
        pq.push(long(1));
        long result = 0;
        for(int i = 0; i < index; ++i){
            // 每次取顶,也就是最小值,弹出
            result = pq.top();
            pq.pop();
            for(int j = 0; j < 3; ++j){
                // 存入235倍数的值
                long temp = result * factors[j];
                // 只存放非重复值
                if(um.find(temp) == um.end()){
                    um[temp] = true;
                    pq.push(temp);
                }
            }
        }
        return int(result);
    }
};

2)动态规划

#include <queue>
class Solution {
public:
    // 获取丑数
    int GetUglyNumber_Solution(int index) {
        // 判空
        if(index == 0){
            return 0;
        }
        // 定义丑数集合
        vector<int> uglyNums = { 1 };
        // 循环按规律找到所有丑数
        int i = 0, j = 0, k = 0;
        int t;
        for(t = 0; t < index; ++t){
            // ijk表示已知丑数乘235的进度
            // 举例说明
            // 1)开始ijk均为0,则从数字1开始,丑数后续依次为2 3 5,其中2最小,则i升为1
            // 2)i为1,即第二个丑数2,用2的2倍也就是4和3 5比较,此时3最小,则j升为1
            // 3)i和j为1,即用第二个丑数2的2倍3倍,即4和6,和5比较,此时4最小,则i继续升为2
            // 4)i为2,j为1,k为0,用3的2倍、2的3倍、1的5倍比较,即6 6 4,此时5最小,则k升为1
            // 5)i为2,j为1,k为1,用3的2倍、2的3倍,2的5倍比较,即6 6 10,此时6最小,i和j同时升1
            // 从上述5步可看到全局规律,ijk是从前往后慢慢推进的,结合了动态规划的思想,后续步进以前面为基准,动态扩展后续丑数
            int num2 = uglyNums[i] * 2;
            int num3 = uglyNums[j] * 3;
            int num5 = uglyNums[k] * 5;
            int minNum = min(num2, min(num3, num5));
            uglyNums.push_back(minNum);
            if(minNum == num2){
                i++;
            }
            if(minNum == num3){
                j++;
            }
            if(minNum == num5){
                k++;
            }
        }
        return uglyNums[t - 1];
    }
};

文章来源:https://blog.csdn.net/zhaitianbao/article/details/134939990
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。