在具有重复项的数组中查找丢失的随机数字量

Question

我应该有一个完整的数字标识符数组，如下所示：

a = [3, 4, 5, 6, 7, 8, 9, 10]

但是，我有一个乱七八糟的数组，顺序随机，有重复和缺失的数字，如下所示：

b = [4, 9, 7, 7, 3, 3]

除了不重复地减去数组之外，是否有更好的方法来找出缺少的数字？

a - b.uniq

Answer 1

(a - b).empty?

有效，但是——取决于数据——它可能不是确定 a 是否包含不在 b 中的元素的最快方法。例如，a 的每个元素不在 b 中的概率很高，平均而言，检查 a[0] 是否在 b 中可能更快，然后（如果不是）如果 a[1] 在 b 中，依此类推，当元素在 b 中时停止。但同样，这取决于数据，特别是 (a - b).empty? 是 true 的可能性。如果这种可能性很大，用 C 编写的 Array#- 将相对较快，并且可能是最佳选择。

另一方面，如果几乎可以肯定 a 将包含许多不在 b 中的元素，那么执行以下操作可能会更快：

require 'set'

b_set = b.to_set
  #=> #<Set: {4, 9, 7, 3}> 
a.all? { |n| b_set.include?(n) }

无论如何，您可以先进行一次廉价测试：

b.size < a.size

如果这是真的，a 中肯定至少有一个元素不在 b 中（假设 a 不包含重复项）。

Answer 2

Ruby 2.6 引入了 Array#difference 在这里看起来很完美：

a = [3, 4, 5, 6, 7, 8, 9, 10]
b = [4, 9, 7, 7, 3, 3]

a.difference(b)
# => [5, 6, 8, 10]

这看起来很方便，而且可读性强。

在具有重复项的数组中查找丢失的随机数字量

Find missing random amount of numbers in array with duplicates

ruby

arrays

algorithm

complexity-theory