Поиск наименьшего значения, появляющегося в двух массивах одновременно в Ruby

Для проекта на Ruby мне нужно сравнить массивы и сохранить наименьшее значение, например:

a = [1, 2, 2, 1]
b = [1, 2, 2, 3]

приведет к [1, 2, 2], потому что 2 появляется как минимум дважды, 1 появляется как минимум один раз, а 3 появляется только в одном массиве.

Я пытался сделать это с помощью оператора &, но он не сохраняет дубликаты:

a & b #=> [1, 2]

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

Может быть, сделать хэш с 0 в качестве значения по умолчанию и сохранить минимальное количество вхождений?

Пошаговое руководство по созданию собственного Slackbot: От установки до развертывания
Пошаговое руководство по созданию собственного Slackbot: От установки до развертывания
Шаг 1: Создание приложения Slack Чтобы создать Slackbot, вам необходимо создать приложение Slack. Войдите в свою учетную запись Slack и перейдите на...
1
0
65
3
Перейти к ответу Данный вопрос помечен как решенный

Ответы 3

Ответ принят как подходящий

Вы можете начать с подсчета каждого появления с помощью подсчета:

a = [1, 2, 2, 1]
b = [1, 2, 2, 3]

h1 = a.tally #=> {1=>2, 2=>2}
h2 = b.tally #=> {1=>1, 2=>2, 3=>1}

Затем оба хэша можно объединить с помощью слияния с блоком, который вызывается всякий раз, когда в обоих хешах существует ключ. Возвращаемое значение блока определяет окончательное значение для этого ключа: (здесь: нижнее значение)

h1.merge(h2) { |k, v1, v2| [v1, v2].min }
#=> {1=>1, 2=>2, 3=>1}

Это уже отлично работает для ключей 1 и 2, но, к сожалению, ключ 3 также присутствует в результате слияния.

Однако, поскольку блок вызывается только для повторяющихся ключей, мы можем использовать небольшую хитрость и вместо этого хранить дубликаты в отдельном хэше: (игнорируя возвращаемое значение из merge)

result = {}
h1.merge(h2) { |k, v1, v2| result[k] = [v1, v2].min }

result
#=> {1=>1, 2=>2}

Чтобы расширить это обратно в массив:

result.flat_map { |k, v| [k] * v }
#=> [1, 2, 2]

Вы можете опустить переменные h1 и h2, встроив их, т.е.

result = {}
a.tally.merge(b.tally) { |k, v1, v2| result[k] = [v1, v2].min }
result
#=> {1=>1, 2=>2}

Вы даже можете включить хэш результата, используя with_object с небольшой помощью enum_for: (хотя это выглядит довольно уродливо)

a.tally.enum_for(:merge, b.tally).with_object({}) { |(k, v1, v2), r| r[k] = [v1, v2].min }
#=> {1=>1, 2=>2}

Еще пара вариантов:

Вот один, использующий flat_map для итерации пересечения a и b;

a = [1, 2, 2, 1]
b = [1, 2, 2, 3]

(a&b).flat_map{ |num| [num] * [a.count(num), b.count(num)].min}
#=>  [1, 2, 2]

Как видите, он использует методы count и min, чтобы выяснить, какой из двух массивов имеет наименьшее количество каждого числа. Числа добавляются к результирующему массиву, кратному этому результату, с помощью Array#*.


И вот очень похожий подход к созданию запрошенного хэша вместо массива;

a = [1, 2, 2, 1]
b = [1, 2, 2, 3]

(a&b).map{ |num| [num, [a.count(num), b.count(num)].min] }.to_h
#=>  {1=>1, 2=>2}

Синтаксис очень похож и использует тот же базовый подход, но на этот раз мы просто использовали стандартный метод map для перебора пересечения a и b. Для каждого соответствующего элемента массива создается новый массив из 2 элементов. Первый элемент — это число, присутствующее в обоих исходных массивах, а второй элемент — это минимальное количество раз, когда это число присутствует либо в a, либо в b. Полученные массивы из 2 элементов затем преобразуются в хэш с помощью Array#.to_h.

Естественный способ сделать это, на мой взгляд, подобен сопоставлению игральных карт из двух рук. Я хотел бы пройти my_hand по одному card за раз, проверяя, if есть ли совпадение в other_hand. Если совпадение найдено, card отнимается от other_hand и записывается как pair. Если совпадений не найдено, то card игнорируется. Используя тот же логический подход, вот что мы можем сделать:

arr_1= [2, 2, 3, 3, 4, 5, 6, 7, 8]
arr_2 = [1, 2, 3, 3, 4, 5, 6]

def find_pairs(my_hand, other_hand)

other_hand = other_hand.dup

pairs = my_hand.select{|card| card & other_hand.delete_at(other_hand.index(card)) if other_hand.include? card}

end

find_pairs(arr_1, arr_2)
#=>  [2, 3, 3, 4, 5, 6]

Здесь он сводится к его критическим элементам и применяется к исходному примеру:

a = [1, 2, 2, 1]
b = [1, 2, 2, 3]

c = b.dup

a.select {|num| num & c.delete_at(c.index(num)) if c.include? num}
#=>  [1, 2, 2]

Я действительно не сторонник создания копии исходного массива, но я не могу придумать никакого другого неразрушающего способа использовать этот подход. Может кто подскажет в комментариях.

Другие вопросы по теме