Ruby 数组减法，无需多次删除项目

Question

Ruby 中规范的 Array 差异示例是:

[ 1, 1, 2, 2, 3, 3, 4, 5 ] - [ 1, 2, 4 ]  #=>  [ 3, 3, 5 ]

获得以下行为的最佳方法是什么？

[ 1, 1, 2, 2, 3, 3, 4, 5 ].subtract_once([ 1, 2, 4 ])  #=>  [ 1, 2, 3, 3, 5 ]

也就是说，只有第二个数组中每个匹配项的第一个实例从第一个数组中移除。

Answer 1

减去值在另一个数组或任何 Enumerable 中出现的次数:

class Array
  # Subtract each passed value once:
  #   %w(1 2 3 1).subtract_once %w(1 1 2) # => ["3"]
  #   [ 1, 1, 2, 2, 3, 3, 4, 5 ].subtract_once([ 1, 2, 4 ]) => [1, 2, 3, 3, 5]
  # Time complexity of O(n + m)
  def subtract_once(values)
    counts = values.inject(Hash.new(0)) { |h, v| h[v] += 1; h }
    reject { |e| counts[e] -= 1 unless counts[e].zero? }
  end

将每个唯一值减去一次:

require 'set'
class Array
  # Subtract each unique value once:
  #   %w(1 2 2).subtract_once_uniq %w(1 2 2) # => [2]
  # Time complexity of O((n + m) * log m)
  def subtract_once_uniq(values)
    # note that set is implemented 
    values_set = Set.new values.to_a 
    reject { |e| values_set.delete(e) if values_set.include?(e) }
  end
end