Сколько раз массив появляется в другом массиве?

Question

Я новичок в Ruby on Rails.Кажется, на этот вопрос отвечают другие языки программирования, но не RoR.

У меня есть массив с 3 элементами.

array1 = [1, 2, 3]

У меня есть элементы в другом массиве, которые я хочу проверить и посмотреть, сколько раз array1 появляется в array2:

array2 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 10, 11, 2, 12, 3]

Ответ должен быть 2.

Answer 1

Другой подход:

array2.each_with_object(array1.product([0]).to_h) do |el, hash|
  hash[el] += 1 if hash.key?(el)
end.each_value.min

Один раз просматривает массив 2, подсчитывает интересующие нас элементы, выбирает минимальное значение.

Используется

array1.product([0]).to_h
 => {1=>0, 2=>0, 3=>0}

для посева стартовых счетчиков.

Answer 2

Точно так же, как @stefan упоминается в комментариях к одному из постов.

Вы также можете создать частотный хеш, чтобы избежать многократного обхода массива.

Чтоэто означает:

frequency_map = Hash.new{|h,k| h[k] = 0 }

array2.each{ |number| frequency_map[number] += 1 }

frequency_map
#=> {1=>2, 2=>2, 3=>2, 4=>1, 5=>1, 6=>1, 7=>1, 8=>1, 9=>1, 10=>1, 11=>1, 12=>1}

Как вы можете видеть выше, у нас есть частота каждого числа в массиве 2 только из одной итерации, то есть O (n) времени, но имеет O (n) пространственную сложность.

Из приведенной частоты мы можем легко определить количество раз, которое array1 появилось в array2:

frequency_of_array1 = nil
array1.each do |number|
  if frequency_of_array1.nil?
    frequency_of_array1 = frequency_map[number]
  else
    frequency_of_array1 = frequency_of_array1 > frequency_map[number] ? frequency_map[number] : frequency_of_array1
  end
end

frequency_of_array1 #=> 2

Или просто так (но построить другой массив / пространство - которого избегаливыше):

array1.map{ |num| frequency_map[num] }.min

Answer 3

Вы можете попробовать следующее:

a1.map { |a1i| a2.count(a1i) }.min

, который вычисляет, как часто каждый элемент в array1 появляется в array2, а затем выбирает минимальное число как число возможных подмассивов без пересечений.

Отрывочное представление моего восприятия предложения @ Стефана:

a1.product([0]).to_h.merge(
  a2.group_by(&:itself).transform_values(&:size)
).values_at(*a1).min

И более разумный:

count_per_a2i = a2.group_by(&:itself).transform_values(&:size)
a1.map { |a1i| count_per_a2i[a1i] }.min_by(&:to_i)