Ruby数组减法，不重复删除项目。

Question

Ruby中典型的数组差示例是：

[ 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 ]

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

- Tom Shaw

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

- glebm

---

我会接受这个，但如果参数可以包含重复值并依次应用（它们被转换为Set时被压缩），那就太好了。不确定如何在保持性能的同时保留重复项。 （我也想接受数组而不是单独的值作为参数，但这很容易更改） - Tom Shaw

我已经更新了答案，使用一个版本来应用重复项，就像它们在另一个数组中出现的次数一样。 - glebm

@glebm 大佬，你的解决方案真是太棒了！这对我帮助很大。你是专门为了回答这个 Stack Overflow 的问题而写的吗？非常感谢你。 - aaron-coding

@affinities23 没关系，新年快乐！我写这个是为了练习，当时刚开始学 Ruby :) - glebm

Answer 2

class Array
  def subtract_once(b)
    h = b.inject({}) {|memo, v|
      memo[v] ||= 0; memo[v] += 1; memo
    }
    reject { |e| h.include?(e) && (h[e] -= 1) >= 0 }
  end
end

我相信这样做可以达到我想要的效果。非常感谢 @glebm。

- Tom Shaw

---

建议：在 inject 方法内部: memo[v] ||= 0; memo[v] += 1; memo 在 reject 方法内部： h.include?(e) && !(h[e] -= 1).zero? - glebm

Answer 3

这是我目前所能想到的全部内容：

[1, 2, 4].each { |x| ary.delete_at ary.index(x) }

- Paige Ruten

---

如果 m（[1,2,4] 的大小）很大，那可能会变得有点慢。 - glebm

这个解决方案仅在ary中包含[1,2,4]数组的每个元素时才有效。否则，该元素的索引为nil。内部可能是这样的：i = ary.index(x); ary.delete_at(i) if i - Matt Sanders

Answer 4

与@Jeremy Ruten的答案类似，但考虑到某些元素可能不存在：

# remove each element of y from x exactly once
def array_difference(x, y)
  ret = x.dup
  y.each do |element|
    if index = ret.index(element)
      ret.delete_at(index)
    end
  end
  ret
end

这个答案也不会修改原始数组，因为它是在操作时进行的。

x = [1,2,3]
y = [3,4,5]
z = array_difference(x, y) # => [1,2]
x == [1,2,3]               # => [1,2,3]

- Matt Sanders