红宝石算法

Question

使用堆在下面的算法工作：

鉴于整数的非空数组，返回k个最频繁的 元素。

例如，给定[1,1,1,2,2,3]和k = 2，返回[1,2]。

注意：您可以假定k总是有效的，1≤k≤独特的 元素的数量。算法的时间复杂度必须优于O（n log n），其中n是数组的大小。

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

MaxHeap回答

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）的做到这一点一个哈希表中间转换：

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而不用担心排名。