紅寶石算法

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