而不删除项目不止一次
的规范数组差异例如更红宝石红宝石阵列减法是:而不删除项目不止一次
[ 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 ]
也就是说,只有第二个数组中的每个匹配项的第一个实例从第一个数组中移除。
数值相加多次,或任何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
这是我能想到的,到目前为止:因为它们出现在其他阵列中
[1, 2, 4].each { |x| ary.delete_at ary.index(x) }
这可能会有点慢,如果'M'(大小[1,2,4])是大 – glebm 2010-10-04 04:49:44
此解决方案仅适用如果[1,2,4]数组的每一个元素是目前在'ary'。否则,该元素的索引是零。里面可能是这样的:'我= ary.index(x); ary.delete_at(i)if i' – 2014-02-12 18:52:50
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
类似@Jeremy流转的的答案,但占的事实,某些元素可能不存在:
# 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]
我打算接受这一点,但如果参数可能包含重复的值(它们会被转换为Set),那么它会很好。不确定如何在保持性能的同时保留重复项。 (另外我想接受一个数组并且不将值作为单独的参数,但是这是一个简单的改变) – 2010-10-04 05:22:27
我已经更新了应用dupes的版本的答案,因为它们出现在另一个数组中。 – glebm 2014-07-20 01:10:40
@glebm辉煌的解决方案男人!这真的帮了我很多。你写这个只是为了回答这个问题?谢谢一堆。 – 2014-12-30 16:34:47