如何在Ruby数组中高效提取重复元素？

Question

我有一个类似于 [1,1,1,2,4,6,3,3] 的数组，我想要获取其中重复的元素列表，例如在这个例子中是 [1,3]。我写了以下代码：

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

但它的效率非常低下（O(n²)）。你有更好的想法吗？如果可能的话，简明扼要。

谢谢。

- MiniQuark

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

- MiniQuark

---

是的，我认为这比我的代码更干净。只是出于好玩，在Ruby >= 1.8.7的情况下，以下是将该方法全部放在一行中的写法。 array.inject(Hash.new(0)){|counts, val| counts.tap{|c| c[val]+=1}}.reject{|val, count| count==1}.keys我认为你的代码更易读，哈哈。 :) - Greg Campbell

我非常、非常喜欢这个解决方案，因为在所有O(n)方案中它是最可读/易懂的。以下是一个单行修改，只是为了好玩：array.inject(Hash.new(0)) { |h, i| h[i] += 1; h }.reject { |v, c| c == 1 }.keys。 - Marek Příhoda

谢谢！太棒了…我一直在苦恼detect，find_all等问题。 - rapcal

这个答案没问题，但是任何认为它是最佳答案的人都需要熟悉Set.new。它在内部使用哈希表，在需要O(1)哈希键访问但又想要数组简单性的情况下非常好用。此外，它有助于可读性，因为所有逻辑都缩小到了明显易懂的dups.add(val) if seen_already.include?(val)。 - Adamantish

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?都是常数时间操作。

- Greg Campbell

Answer 3

像这样的东西怎么样？它的时间复杂度为 O(n)。

a = [1,1,1,2,4,6,3,3]
b = {}
a.each { |v| if b.has_key? v then b[v] = b[v]+1 else b[v]=1 end }
b.reject { |k,v| if v > 1 then false else true end }.keys

- Ilya Haykinson

---

我喜欢这个想法。你可以像这样美化最后一行：b.reject{|k,v| v==1}.keys - MiniQuark

另外，你可以使用 b=Hash.new(0) ，这样你就可以有一个更简单的第三行代码: a.each{|v|b[v]+=1} - MiniQuark

Answer 4

一个O(n)的解决方案（将<< x改为+ [x]，将update改为merge以使其纯函数化）：

rs = xs.inject([[], {}]) do |(out, seen), x| 
  [(seen[x] == 1 ? (out << x) : out), seen.update(x => (seen[x] || 0)+1)]
end[0]

一个更简单但空间效率较低的方法：

rs = xs.group_by { |x| x }.select { |y, ys| ys.size > 1 }.keys

使用“列表推导式”避免中间哈希的相同思路：

rs = xs.group_by { |x| x }.map { |y, ys| y if ys.size > 1 }.compact

- tokland

---

这个解决方案存在问题。请查看 xs = [1,1,1]。 - Jan

group_by会更适合，不是吗？ - Andrew Grimm

@Andrew。我以为已经有一个使用group_by的解决方案了，但似乎是在另一个问题中。我会添加它。现在Ruby有有序哈希，我们可以保留原始可枚举对象的顺序。然而，这比自定义解决方案的空间效率要低。 - tokland

Answer 5

使用 inject

[1,1,1,2,4,6,3,3].inject({}){ |ele, n| ele[n] = nil; ele }.keys 
# => [1, 2, 4, 6, 3] 

解释：

ele哈希初始值为{}，每次迭代都会向ele哈希中添加一个键为数字n和值为nil的元素。在最后，ele作为返回结果:

{1=>nil, 2=>nil, 4=>nil, 6=>nil, 3=>nil}

我们只需要键值，所以.keys就可以完成任务。

- ivanxuu

---

谢谢，但我只需要重复的元素，就像示例中所示。 - MiniQuark

Answer 6

我在思考如何计算数组中唯一元素出现的次数。 这可能像原始建议一样非常低效，但是看着这个问题很有趣。 我没有针对更大的数组进行任何基准测试，所以这只是一个练习。

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

dupes = []
a.uniq.each do |u|
  c = a.find_all {|e| e == u}.size
  dupes << [u, c] unless c == 1
end

puts dupes.inspect

# dupes = [[1, 3], [3, 2]]
# 1 appears 3 times
# 3 appears twice


# to extract just the elment a bit cleaner
dupes = a.uniq.select do |u|
  a.find_all {|e| e == u}.size != 1
end
puts dupes.inspect
# returns [1,3]

- marekj

Answer 7

如果重复的条目总是连续的，就像您的示例一样，那么这将起作用；否则，您必须先进行排序。each_cons检查指定大小的滚动窗口。

require 'set'

my_array = [1,1,1,2,4,6,3,3]
dups = Set.new
my_array.each_cons(2) {|a,b| dups.add(a) if (a == b)}
p dups.to_a

- Justin Love

Answer 8

一些想法：你需要找出正确的库数据结构：

1 对数组进行排序O(nlogn)，然后遍历整个数组

2 创建一个集合，搜索当前数组元素是否在集合中存在，如果不存在，则插入并继续处理所有元素--再次O(nlogn)。

- dirkgently