在 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.

我最初的冲动是使用散列table 将数字作为键，将值作为出现次数。然后，我可以将每个键值对作为一个节点插入到 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)

总结

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

Answer 2

你总是可以用几个 O(n) 转换和一个散列-table 中间来做到这一点：

def max_in_list(list, n = 1)
  list.group_by { |v| v }.sort_by do |_, s|
    -s.length
  end.first(n).map(&:first)
end

numbers = [ 1, 1, 1, 1, 2, 2, 2, 3, 3, 4, 4, 4, 5, 5, 6 ]

max_in_list(numbers, 2)
# => [1, 2, 4]

不幸的是，max_by 在请求多个条目时不遵守顺序。它只给出最高 N，而不关心排名。

在 ruby 算法中使用堆

Using heap in ruby algorithm

ruby

algorithm

heap

hashtable

nodes