【LeetCode每日一题】264. 丑数 II

公众号guangcity

发布于 2021-04-22 11:36:24

2280

发布于 2021-04-22 11:36:24

文章被收录于专栏：光城(guangcity)

【LeetCode每日一题】264. 丑数 II

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

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

示例 1：

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

题解：

解法1：直接生成所有数据，取出对应的元素即可。如果采用递归，肯定会TL，这里采用迭代。

class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> data;
        int i = 1;

        for (long long i=1; i<INT_MAX; i*=2) {
            for (long long j=i; j<INT_MAX; j*=3) {
                for (long long k=j; k<INT_MAX; k*=5) {
                    data.push_back(k);
                }
            }
        }
        sort(data.begin(), data.end());
        return data[n-1];
    }
   
};

解法2：堆与去重

类似于二叉树的层次遍历，入队操作是以小到大，从堆中出来的每次是最小的，当出来n次时，则结束。

注意：入堆时有重复元素就不要入堆了，因为这样会多算。

class Solution {
public:
    typedef long long LL;
    int nthUglyNumber(int n) {
        set<LL> s;
        priority_queue<LL, vector<LL>, greater<LL>> pq;
        s.insert((LL)1);
        pq.push((LL)1);
        int ans = 1;
        vector<int> factor{2, 3, 5};
        while (n--) {
            LL cur = pq.top(); pq.pop();
            ans = (int)cur;
            // [2,3,5]
            for (auto x : factor) {
                LL mu = cur*x;
                if (s.count(mu)) continue;
                s.insert(mu);
                pq.push(mu);
            }
        }
        return ans;
    }
   
};

解法3：动态规划及三指针。

dp[i]表示第i个丑数，那么dp[i]的转移来自于：

dp[p2]*2、dp[p3]*3、dp[p5]*5

实现：

class Solution {
public:
    typedef long long LL;
    int nthUglyNumber(int n) {
        vector<LL> dp(n+1, 0x3f3f3f3f);
        dp[1] = 1;
        int p2 = 1, p3 = 1, p5 = 1;
        for (int i = 2; i <= n; i++) {
            LL n2 = dp[p2] * 2, n3 = dp[p3] * 3, n5 = dp[p5] * 5;
            dp[i] = min(min(n2, n3), n5);
            if (dp[i] == n2) {                    
                p2++;
            } 
            if (dp[i] == n3) {
                p3++;
            } 
            if (dp[i] == n5) {
                p5++;
            }
        }
        return dp[n];
    }
   
};