Leetcode 醜數

LC 264. 醜數 II

題目：你一個整數 n ，請你找出并傳回第 n 個 醜數 。醜數 就是隻包含質因數 2、3 和/或 5 的正整數。

方法：介紹三種方法，從最直覺的開始

方法一：堆+歐拉篩

每次從堆中取一個最小的，然後分别乘2，3，5進行擴充。每次取出的最小值加入答案，需要去重。

有大量的重複，需要歐拉篩優化才能過

class Solution {
public:
    typedef long long ll;
    int nthUglyNumber(int n) {
        vector<ll>primes = {2, 3, 5};
        priority_queue<ll, vector<ll>, greater<ll>>pq;
        pq.push(1);
        set<ll>res;
        while(res.size() < n) {
            ll p = pq.top();pq.pop();
            res.insert(p);
            for(int prime : primes) {
                pq.push(prime * p);
                if(p % prime == 0)  break;  // 必需的優化，歐拉篩，p是由prime擴充來的
            }
        }
        return *(--res.end());  // 集合中的最後一個
    }
};
           

方法二：二分

考慮第i個元素是如何生成的，肯定是從已經生成的元素中找到一個值，其乘以2/3/5的值大于且最接近第i-1個。

對于2，我們可以從第一個開始枚舉，直到超過第i-1元素，3、5同理；

然後取三者的最小值

由于已生成的數組是有序的，是以可以二分查找

class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int>dp;
        dp.push_back(1);
        for(int i = 1;i < n;i++) {
            int a = *upper_bound(dp.begin(), dp.end(), dp[dp.size()-1]/2) * 2;
            int b = *upper_bound(dp.begin(), dp.end(), dp[dp.size()-1]/3) * 3;
            int c = *upper_bound(dp.begin(), dp.end(), dp[dp.size()-1]/5) * 5;
            dp.push_back(min(a, min(b, c)));
        }
        return dp[n-1];
    }
};
           

方法三：三指針

我們從方法二中得到啟發，可以發現，二分查找到的點總是往右移的，且如果未采用這個點的值說明該點還未被使用，點不用右移；使用的就右移一位。

class Solution {
public:
    int nthUglyNumber(int n) {
        int i2 = 0, i3 = 0, i5 = 0;
        vector<int>dp(n, 0);
        dp[0] = 1;
        for(int i = 1;i < n;i++) {
            dp[i] = min(dp[i2]*2, min(dp[i3]*3, dp[i5]*5));
            if(dp[i] == dp[i2]*2)  i2++;
            if(dp[i] == dp[i3]*3) i3++;  // 不能用else if，為了去重
            if(dp[i] == dp[i5]*5) i5++;
        }
        return dp[n-1];
    }
};
           

LC 313. 超級醜數

題目：與上題相比，不隻2,3,4，而是由一個primes數組

方法：堆+歐拉篩

class Solution {
public:
    typedef long long ll;
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        priority_queue<ll, vector<ll>, greater<ll>>pq;
        pq.push(1);
        set<ll>res;
        while(res.size() < n) {
            ll p = pq.top();pq.pop();
            res.insert(p);
            for(int prime : primes) {
                pq.push(prime * p);
                if(p % prime == 0)  break;  // 歐拉篩，p是由prime擴充來的
            }
        }

        return *(--res.end());  // 集合中的最後一個
    }
};
           

當然，也可以使用上面兩種方法。

個性簽名：時間會解決一切