Найти пропущенное случайное количество чисел в массиве с дубликатами

Question

У меня должен быть полный массив числительных c идентификаторов, подобных этому:

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. Если эта вероятность велика, Array # - , который записан в C, будет относительно быстрым и, вероятно, лучшим выбором.

С другой стороны, если его все, кроме определенного что 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]

Кажется удобным для этого, с дополнительным преимуществом очень удобочитаемости.