ruby - 查找两个数组之间的精确值重叠

Question

我有两个数组

a1 = [1, 1, 1, 2, 3, 3, 3]
a2 = [1, 1, 3, 3, 5, 5]

我想返回出现在两个数组中的值以及它们出现的确切数量

# => [1, 1, 3, 3]

我不能使用a1 & a2，因为这将返回唯一值（[1, 3]）

实现这一目标的最佳方法是什么？

标签： ruby

Answer 1

看起来你所拥有的并不是真正的数组，它们是multisets或bag。

编程中有一条一般规则：如果你选择正确的数据表示，你的算法就会变得更简单。

因此，如果您使用多重集而不是数组，您的问题将变得微不足道，因为您正在寻找的实际上只是两个多重集的交集。

不幸的是，核心或标准库中没有多集实现，但网络上有几个多集 gem。例如，有multimap gem，它也包括一个多重集。不幸的是，它需要一点爱和关怀，因为它使用了只能在 YARV 2.2 之前使用的 C 扩展。还有multiset gem。

require 'multiset'

m1 = Multiset.new(a1)
#=> #<Multiset:#3 1, #1 2, #3 3>

m2 = Multiset.new(a2)
#=> #<Multiset:#2 1, #2 3, #2 5>

m = m1 & m2
#=> #<Multiset:#2 1, #2 3>

就个人而言，我不太喜欢inspect输出，但我们可以看到发生了什么并且结果是正确的：m包含 2 ×1和 2 × 3。

如果你真的需要结果作为一个Array，你可以使用Multiset#to_a：

m.to_a
#=> [1, 1, 3, 3]