Каноническая массив отличие, например, в Рубине:Рубин массив вычитание без удаления элементов больше, чем когда-то
[ 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
Это решение работает только, если каждый элемент [1,2,4] массива присутствовать в 'ary'. В противном случае индекс элемента равен нулю. Внутри может быть что-то вроде: 'i = ary.index (x); ary.delete_at (i) если i' –
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 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]
Я собираюсь принять это, но было бы неплохо, если бы аргумент мог содержать повторяющиеся значения, которые будут применяться в свою очередь (они становятся раздавленными преобразованием в Set). Не уверен, как вы можете сохранить дубликаты, сохраняя при этом производительность. (Также я хотел принять массив, а не значения как отдельные аргументы, но это простое изменение). –
Я обновил ответ с помощью версии, которая применяет обманки столько раз, сколько они присутствуют в другом массиве. – glebm
@glebm блестящий решение человек! Это очень помогло мне. Вы написали это просто, чтобы ответить на этот вопрос? Огромное спасибо. –