ruby - 在 ruby​​ 算法中使用堆

Question

正在研究以下算法:

Given a non-empty array of integers, return the k most frequent elements.

For example, Given [1,1,1,2,2,3] and k = 2, return [1,2].

Note: You may assume k is always valid, 1 ≤ k ≤ number of unique elements. Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

我最初的冲动是使用哈希表，以数字为键，以值作为出现次数。然后，我可以将每个键值对作为一个节点插入到 maxHeap 中，然后简单地删除 max 直到 k == 0。

构建节点并输入 maxHeap 是否是使用该方法解决问题的正确方法？ 请注意，我对更优化的解决方案并不好奇——好奇我是否会采用这种方式来实现使用 maxHeap 重复查找具有最大出现次数的数字的想法。 节点部分看起来有点矫枉过正，但我​​不确定还能怎么做。

Answer 1

答案:

代码:

input = [1,1,1,2,2,3]
k = 2

def most_frequent(arr, num = 1)
  arr.group_by(&:itself).sort_by {|_,s| -s.length}.first(num).map(&:first)
end

most_frequent(input, k)

输出:

=> [1, 2]

最大堆答案

require "rubygems"
require "algorithms"

include Containers

input = [1,1,1,2,2,3] 
k = 2

def heap_most_frequent(arr, num = 1)
  max_heap = MaxHeap.new(arr.group_by(&:itself).map{|n,ns| [ns.count,n]})
  (1..num).each_with_object([]) { |i, result| result << max_heap.pop[1]}
end

基准:

            user     system      total        real
orig:   0.050000   0.000000   0.050000   (0.057158)
heap:   0.110000   0.000000   0.110000   (0.112387)

总结

大部分工作都用于生成哈希，在这种情况下，堆在处理键值对时只会使事情复杂化。