сортировка по частоте появления в массиве

Question

Есть ли эффективный способ сделать это. У меня есть массив

a=[1,2,2,3,1,2] 

Я хочу вывести частоту появления в порядке возрастания. Пример

[[3,1],[1,2],[2,3]] 

Вот мой код в рубине.

b=a.group_by{|x| x} 
out={} 

b.each do |k,v| 
    out[k]=v.size 
end 

out.sort_by{|k,v| v} 

Answer 1

a = [1,2,2,3,1,2] 
a.each_with_object(Hash.new(0)){ |m,h| h[m] += 1 }.sort_by{ |k,v| v } 
#=> [[3, 1], [1, 2], [2, 3]] 

Answer 2

использовать хэширование, создать хеш, пересечь массив, для каждого числа в массиве, обновить счет в хэше. это займет линейное время O (n), а пространственная сложность будет равна хранению хэша O (n).

Answer 3

Что-то вроде этого:

x = a.inject(Hash.new(0)) { |h, e| h[e] += 1 ; h }.to_a.sort{|a, b| a[1] <=> b[1]} 

Answer 4

Вы пытаетесь разработать алгоритм или вы просто хотите работу? В последнем случае, не изобретайте колесо:

require 'facets' 
[1, 2, 2, 3, 1, 2].frequency.sort_by(&:last) 
# => [[3, 1], [1, 2], [2, 3]] 

Answer 5

def frequency(a) 
    a.group_by do |e| 
    e 
    end.map do |key, values| 
    [key, values.size] 
    end 
end 

a = [1, 2, 2, 3, 1, 2] 
p frequency(a).sort_by(&:last)