For speed, I would do the following, which requires only one pass through each of the two arrays. This method preserves order. I will first present code that does not mutate the original array, then show how it can be easily modified to mutate.
arr = [1,1,1,2,2,3,1]
removals = [1,3,1]
h = removals.group_by(&:itself).transform_values(&:size)
#=> {1=>2, 3=>1}
arr.each_with_object([]) { |n,a|
h.key?(n) && h[n] > 0 ? (h[n] -= 1) : a << n }
#=> [1, 2, 2, 1]
arr
#=> [1, 1, 1, 2, 2, 3, 1]
To mutate arr write:
h = removals.group_by(&:itself).transform_values(&:count)
arr.replace(arr.each_with_object([]) { |n,a|
h.key?(n) && h[n] > 0 ? (h[n] -= 1) : a << n })
#=> [1, 2, 2, 1]
arr
#=> [1, 2, 2, 1]
This uses the 21st century method Hash#transform_values (new in MRI v2.4), but one could instead write:
h = Hash[removals.group_by(&:itself).map { |k,v| [k,v.size] }]
or
h = removals.each_with_object(Hash.new(0)) { | n,h| h[n] += 1 }