Ugly Number II

程序员文章站 2022-04-24 15:33:40

...

Ugly Number II

1. 解析

题目大意，求解第n个ugly数(仅仅包含因子2,3,5的正整数，除1之外).

2.分析

刚开始看到这道题，我的第一反应是优先队列，蓝桥杯也出现过这道题。优先队列最重要的一个性质：队首是整个队列的最值，这道题让我们取第n个数，所以得把队首设置为整个队列中的最小值，为了防止加载重复的元素，利用hashtable存储已经出现过的元素即可解决，每次取队首，然后依次和2,3,5因子相乘，如果出现过，则检测下一个.....依次进行，直到取到第n-1个元素，则队首即为第n个数.

class Solution {
public:
    int nthUglyNumber(int n) {
        priority_queue<long long, vector<long long>, greater<long long>> matrix;
        map<long long, bool> exist;
        matrix.push(1);
        vector<int> factors{{2, 3, 5}};
        while (--n > 0){
            long long ele = matrix.top();
            matrix.pop();
            for (auto fac: factors) {        
                if (exist.count(ele * fac)) continue;
                exist[ele * fac] = true;
                matrix.push(ele * fac);
            }
        }
        return matrix.top();
    }
};

3.高效解法

参考Grandyang博主，好多题目都是参考他的，很感谢，提供很清晰的思路。

将其划分为3个子矩阵进行求解，如下

(1) 1*2 = 2 2*2 = 4 2*2 = 4 3*2 = 6 3*2 = 6 4*2 = 8 5*2 = 10 5*2 = 10 6*2 = 12 ......

(2) 1*3 = 3 1*3 = 3 2*3 = 6 2*3 = 6 2*3 = 6 3*3 = 9 3*3 = 9 4*3 = 12 4*3 = 12 ......

(3) 1*5 = 5 1*5 = 5 1*5 = 5 1*5 = 5 2*5 = 10 2*5 = 10 2*5 = 10 2*5 = 10 3*5 = 15 ......

class Solution {
public:
    int nthUglyNumber(int n){
        vector<int> res(1, 1);
        int i2 = 0, i3 = 0, i5 = 0;
        while (res.size() < n){
            int m2 = res[i2] * 2, m3 = res[i3] * 3, m5 = res[i5] * 5;
            int mn = min(m2, min(m3, m5));
            if (mn == m2) i2++;
            if (mn == m3) i3++;
            if (mn == m5) i5++;
            res.push_back(mn);
        }
        return res.back();
    }
};