如何有效地提取Ruby数组中的重复元素？

Question

我有一个类似[1,1,1,2,4,6,3,3]的数组,我想得到重复元素的列表,在本例中为[1,3].我写了这个:

my_array.select{|obj|my_array.count(obj)>1}.uniq

但它的效率很低(o(n²)).你有更好的主意吗？如果可能简洁.

谢谢

Answer 1

灵感来自Ilya Haykinson的回答:

def repeated(array)
  counts = Hash.new(0)
  array.each{|val|counts[val]+=1}
  counts.reject{|val,count|count==1}.keys
end

Answer 2

使用Ruby的Set库:

require 'set'

ary = [1,1,1,2,4,6,3,3]
dups = Set.new
test_set = Set.new
ary.each {|val| dups.add(val) unless test_set.add?(val)}
dups.to_a # [1, 3]

我相信这应该是O(n),因为Set#add和Set#add？据我所知,是恒定时间操作.