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)