Structured solution


  • 0
    Q
    class Product_prime
    {
        const vector<int> &m_ugly_number;
        const int m_base;
        int cur_idx;
      public:
        Product_prime(vector<int> &ugly_number, int base) :
            m_ugly_number(ugly_number), m_base(base), cur_idx(0) {}
    
        int front()
        {
            assert(cur_idx < m_ugly_number.size());
            int res;
            while (true)
            {
                res = m_ugly_number[cur_idx] * m_base;
                if (res != m_ugly_number.back()) //prevent from duplicate result
                    break;
                next();
            }
            return res;
        }
        void next()
        {
            ++cur_idx;
            assert(cur_idx < m_ugly_number.size());
        };
    };
    
    
    class Solution {
      public:
        int nthSuperUglyNumber(int n, vector<int>& primes) {
            vector<int> ugly_number = {1};
            vector<Product_prime> pu;
    
            for (int p: primes)
                pu.push_back(Product_prime(ugly_number, p));
    
            while (ugly_number.size() < n)
            {
                auto it = min_element(pu.begin(), pu.end(),
                                      [] (Product_prime &pp1, Product_prime &pp2)
                                      {
                                          return pp1.front() < pp2.front();
                                      });
    
                ugly_number.push_back(it->front());
                it->next();
            }
    
            return ugly_number.back();
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.