Ruby是否有内置方法实现数组按匹配数量移除元素？

需求背景 #

Ruby内置的数组减法运算符-会移除左侧数组中所有出现在右侧数组里的元素，比如：

# 内置减法的效果：移除所有a和c
%i[a b a b a c] - %i[a c] # => [:b, :b]

但我们需要的是按右侧数组的元素数量，精确移除对应次数的匹配项——也就是只移除1个a和1个c，得到结果[:b, :a, :b, :a]。

你的实现的问题 #

你写的方法思路可行，但效率偏低：每次遍历都用rem.index(val)做线性查找，还通过数组拼接rem[0...idx].concat(rem[idx+1..])修改剩余数组，这两个操作都是O(m)复杂度（m是右侧数组剩余长度），当数组规模较大时，整体时间复杂度会达到O(n*m)，性能会明显下降。

更高效的实现方式 #

可以通过哈希统计元素出现次数来优化，时间复杂度降到O(n + m)，代码更简洁且性能更好：

def remove(lhs, rhs)
  # 统计右侧数组各元素的出现次数
  element_counts = rhs.tally
  # 遍历左侧数组，构建结果
  lhs.each_with_object([]) do |val, result|
    # 如果当前元素还有剩余可移除次数，就减少计数，否则加入结果
    if element_counts[val]&.positive?
      element_counts[val] -= 1
    else
      result << val
    end
  end
end

# 测试效果
remove(%i[a b a b a c], %i[a c]) # => [:b, :a, :b, :a]

代码说明 #

1. rhs.tally是Ruby 2.7+新增的方法，会返回一个哈希，键是数组元素，值是该元素在数组中出现的次数；如果用更低版本Ruby，可以手动统计：element_counts = Hash.new(0); rhs.each { |v| element_counts[v] += 1 }。
2. each_with_object([])遍历左侧数组，同时构建结果数组，避免额外的变量声明。
3. element_counts[val]&.positive?用安全导航符避免nil报错，判断当前元素是否还有可移除的次数。

如果想要更简洁的写法（但效率略低于哈希方法），也可以这样写：

def remove(lhs, rhs)
  rhs_copy = rhs.dup
  lhs.reject do |val|
    idx = rhs_copy.index(val)
    rhs_copy.delete_at(idx) if idx
  end
end

这个写法和你的思路类似，但用reject和delete_at简化了逻辑，不过依然存在线性查找的问题，适合小规模数组使用。

内容的提问来源于stack exchange，提问作者GSP