Two solutions with Bucket Sort O(N) and Priority Queue O(NlogK)


  • 0
    I

    I believe this problem is waiting a Priority Queue solution, as it says

    Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

    So I implement a minimum heap first, with time complexity O(NlogK).

      # O(NlogK) using minimum priority queue
      def top_k_frequent(nums, k)
        counter = nums.reduce( Hash.new(0) ) do |ha, num|
          ha[num] += 1
          ha
        end
    
        pg = PriorityQueue.new
        pair = Struct.new(:key, :value)
    
        counter.each do |num, count|
          node = pair.new(count, num)
    
          if pg.size < k
            pg.insert node
          else
            next if node.key <= pg.get_min.key
    
            pg.delete_min
            pg.insert node
          end
        end
    
        # puts "pg: #{pg.array} size: #{pg.size}"
    
        # generate results
        results = []
        while pg.size > 0
          results.unshift pg.delete_min
        end
    
        # puts "results: #{results}"
    
        results.map(&:value)
      end
    
    # A minimum priority queue
    class PriorityQueue
      attr_accessor :array, :size
    
      def initialize
        @array = [nil]
        @size = 0
      end
    
      def insert(node)
        self.size += 1
        array[size] = node
        swim(size)
      end
    
      def delete_min
        res = get_min
    
        swap(1, size)
        self.size -= 1
        sink(1)
    
        res
      end
    
      def get_min
        array[1]
      end
    
      private
    
        def swim(k)
          while k/2 >= 1
            j = k/2
    
            break if !less(k, j)
    
            swap(j, k)
            k = j
          end
        end
    
        def sink(k)
          while 2*k <= size
            j = 2*k
            j += 1 if j+1 <= size && less(j+1, j)
    
            break if !less(j, k)
    
            swap(j, k)
            k = j
          end
        end
    
        def less(j, k)
          array[j].key < array[k].key
        end
    
        def swap(j, k)
          t = array[j]; array[j] = array[k]; array[k] = t
        end
    
    end
    
    

    Then I noticed that Bucket Sort can also solve the problem, within linear time. Good!

      # O(N) using bucket sort
      def top_k_frequent(nums, k)
        counter = nums.reduce( Hash.new(0) ) do |ha, num|
          ha[num] += 1
          ha
        end
    
        # puts "counter: #{counter}"
    
        max_count = 0
        frequency = counter.reduce( Hash.new{|hh,kk| hh[kk] = Array.new } ) do |ha, (num, count)|
          max_count = count if max_count < count
          ha[count] << num
          ha
        end
    
        # puts "frequency: #{frequency}"
    
        results = []
        max_count.downto(1) do |count|
          break if results.count == k
    
          while !frequency[count].empty? && results.count < k
            results << frequency[count].shift
          end
        end
    
        results
      end
    

    P.S. Quick Select could also work, estimated time complexityO(KN)


Log in to reply
 

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