High Quality C++ with comments (using a Heap)


  • 0
    G
    class Solution {
    public:
    
        template <typename T,typename Comp>
        void MakeHeap(vector<T> &H,const Comp &C)
        {
            make_heap(H.begin(),H.end(),C);
        }
        
        template <typename T, typename Comp>
        void PopHeap(vector<T> &H,const Comp &C)
        {
            pop_heap(H.begin(),H.end(),C);
            H.pop_back();
        }
            
        
        // P - prime
        // I- index
        // V - value
        struct Element
        {
          int P;
          int I;
          int V;
          
          Element(int Pr,int In, int Vl)
          :
          P(Pr),
          I(In),
          V(Vl)
          {
          }
          
          //
          // will be called by std::greater<Element>
          //
          friend bool operator>(const Element &E1, const Element &E2)
          {
              return E1.V > E2.V;
          }
          
        };
        
        int nthSuperUglyNumber(int n, vector<int>& primes) 
        {
            vector<Element> Heap;
            vector<int> Result(n,1);
            
            for(auto &p : primes)
            {
                Heap.push_back(Element(p,0,p));
            }
            
            MakeHeap(Heap,std::greater<Element>());
            
            for(int i = 1; i < n; ++i)
            {
                Element Next = Heap[0];
                
                PopHeap(Heap,std::greater<Element>());
                
                Result[i] = Next.V;
                
                Heap.push_back(Next);
                
                for(int j = 0; j < Heap.size(); ++j)
                {
                    if(Heap[j].V == Next.V)
                    {
                        Heap[j].I++;
                        Heap[j].V = Heap[j].P * Result[Heap[j].I];
                    }
                }
                
                MakeHeap(Heap,std::greater<Element>());
            }
            
            return Result[n - 1];
        }
    };

Log in to reply
 

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