Super Ugly Number | LeetCode

題目的意思就是根據給定的素數數組為因子，求第n個醜數。解法其實和ugly number II 差不多，隻不過輸入的素數個數是不确定的。最簡單的方法就是枚舉，直到找到第N個醜數，但是因為你不知道輸入的因子，是以你枚舉的數量就需要非常大，效率也就會變得非常糟糕。

還是利用之前的方法，重複的利用已經計算出來的醜數來确定下一個醜數，直到找到第N個。首先，我們需要确定到底有幾個素數因子，下一個醜數一定是之前的某個醜數乘以某個素數因子得到的，是以我們可以枚舉出是以目前醜數分别乘以素數因子得到的新醜數，然後選取剛好大于目前最大醜數的數為下一醜數。這裡還是同樣的問題，随着醜數的數量的增多，計算得到的新醜數的量也不斷增加，有沒有啥方法能夠減少計算量。我們可以為每個素數因子維護一個最小索引值。這個最小索引值代表的意思就是，該素數因子乘以對應索引為的醜數剛好能夠大于目前所得到的最大醜數。這樣，每一次我們隻需要從這些醜數中選取最小的，就是下一個醜數。 代碼如下：

class Solution {

public:

    long long nthSuperUglyNumber(int n, vector<int>& primes) {

        if(n==1)

            return 1;

        int size = primes.size();

        vector<int> index(size,0);

        vector<long long> ugly;

        ugly.push_back(1);

        //每次都需要記錄所有因子對應的最小索引（這個數乘以對應因子一定大于目前獲得的ugly number，每次選取最小的）

        int cur = 0;

        while(cur < n){

            vector<long long> temp(size);

            for(int i=0;i<size;++i){

                temp[i]=ugly[index[i]]*primes[i];

            }

            auto m = min_element(temp.begin(),temp.end());

            //取出最小的數并加入到ugly中

            ugly.push_back(*m);

            //更新index中的最小索引

            for(int i=0;i<size;++i){

                while(ugly[index[i]]*primes[i]<=*m){

                    ++index[i];

                }

            }

            ++cur;

        }

        return ugly[n-1];

    }

};