Heap solution would be TLE


  • 0
    I

    As this is an extension of problem 264. Ugly Number II, we could just generalise from it.

    While, in my opinion, the hard (weird) part is that I've got several TLEs.

    Plain O(nk) solution

    TLE version

      # Plain O(n*k)
      def nth_super_ugly_number(n, primes)
        numbers = [1]
    
        # TLE by this (expensive) hash
        primes_and_ids = primes.reduce({}){|ha, prime| ha[prime] = 0; ha }
    
        (n-1).times do
          candidates = primes_and_ids.map{|prime, id| [ prime, prime * numbers[id] ]}
          min = candidates.map(&:last).min
    
          candidates.each do |prime, candidate|
            next unless candidate == min
            primes_and_ids[prime] += 1
          end
    
          numbers << min
        end
    
        numbers[n-1]
      end
    
    

    I used a hash above, which might be a little expensive with massive inputs. So I replaced it with an array. Got passed.

      # Plain O(n*k)
      def nth_super_ugly_number(n, primes)
        numbers = [1]
    
        idx = [0]*primes.count
    
        (n-1).times do
          min = primes.map.with_index{|prime, i| prime * numbers[ idx[i] ] }.min
    
          primes.each_with_index do |prime, i|
            next unless min == prime * numbers[ idx[i] ]
            idx[i] += 1
          end
    
          numbers << min
        end
    
        numbers[n-1]
      end
    

    Heap Solution (TLE)

    Using a Priority Queue (a minimum heap) aims to improves this linear searching code:

    min = primes.map.with_index{|prime, i| prime * numbers[ idx[i] ] }.min
    

    While, just as vcoderld said in Java three methods, 23ms, 36 ms, 58ms(with heap), performance explained

    Besides, the remain part (the inner loop) takes complexity between Nlog(K) and NKlog(K), i.e for the best case there is only one peek == next, it takes log(K), and for the worst case, all objects in the heap == next, so it takes Klog(K). So this loop is not necessarily < KN. That's why the heap solution is slower than the KN solution.

    It's true to take O(nklogk) in the worst case, when all elements have equal keys in heap (delete then insert). But I'm doubted of the test cases. Ok, leave my TLE minimum heap code as a note

    class PriorityQueue
      attr_accessor :array, :n, :comparison
    
      def initialize(arr = [], &comparison)
        @n = arr.length
    
        @array = arr
        @array.unshift nil
    
        @comparison = comparison || ->(a,b){ a < b }
    
        build
      end
    
      def insert(node)
        self.n += 1
        array[n] = node
        swim(array, n, n)
      end
    
      def delete_min
        return nil if n < 1
    
        min = array[1]
    
        swap(array, 1, n)
        self.n -= 1
        sink(array, 1, n)
    
        return min
      end
    
      def get_min
        return nil if n < 1
    
        array[1]
      end
    
      def size
        n
      end
    
      private
    
        def build
          (n/2).downto(1) do |k|
            sink(array, k, n)
          end
        end
    
        def swap(array, i, j)
          t = array[i]; array[i] = array[j]; array[j] = t
        end
    
        def sink(array, k, n)
          while 2*k <= n
            j = 2*k
            j += 1 if j+1 <= n && less(j+1, j)
    
            break if !less(j, k)
    
            swap(array, j, k)
            k = j
          end
        end
    
        def swim(array, k, n)
          while k/2 >= 1
            j = k/2
    
            break if !less(k, j)
    
            swap(array, j, k)
            k = j
          end
        end
    
        def less(i, j)
          comparison[ array[i], array[j] ]
        end
    end
    
      # Use Priority Queue O(n*logk)
      def nth_super_ugly_number(n, primes)
        numbers = [1]
    
        idx = [0]*primes.count
    
        pair = Struct.new(:key, :value)
        candidates = primes.map do |prime|
          key   = prime # prime*numbers[0]
          value = prime
          pair.new(key, value)
        end
        # Minimum heap
        heapq = PriorityQueue.new(candidates){|a,b| a.key < b.key}
    
        (n-1).times do
          min = heapq.get_min.key
          numbers << min
    
          while min == heapq.get_min.key
            min_pair = heapq.delete_min
            prime    = min_pair.value
    
            i = primes.index(prime)
            idx[i] += 1
    
            new_pair = pair.new( prime * numbers[ idx[i] ], prime )
            heapq.insert(new_pair)
          end
    
        end
    
        numbers[n-1]
      end
    
    

Log in to reply
 

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