Как найти и вернуть повторяющееся значение в массиве

arr это массив строк:

["hello", "world", "stack", "overflow", "hello", "again"]

Какой простой и элегантный способ проверить наличие arrдубликатов и, если да, вернуть один из них (неважно, какой)?

Примеры:

["A", "B", "C", "B", "A"]    # => "A" or "B"
["A", "B", "C"]              # => nil

a = ["A", "B", "C", "B", "A"]
a.detect{ |e| a.count(e) > 1 }

Я знаю, что это не очень элегантный ответ, но мне это нравится. Это красивый код лайнера. И работает отлично, если вам не нужно обрабатывать огромный набор данных.

Ищете более быстрое решение? Ну вот!

def find_one_using_hash_map(array)
  map = {}
  dup = nil
  array.each do |v|
    map[v] = (map[v] || 0 ) + 1

    if map[v] > 1
      dup = v
      break
    end
  end

  return dup
end

Он линейный, O (n), но теперь ему нужно управлять несколькими строками кода, тестами и т. Д.

Если вам нужно еще более быстрое решение, попробуйте C.

А вот суть, сравнивающая различные решения: https://gist.github.com/naveed-ahmad/8f0b926ffccf5fbd206a1cc58ce9743e

Вы можете сделать это несколькими способами, причем первый вариант самый быстрый:

ary = ["A", "B", "C", "B", "A"]

ary.group_by{ |e| e }.select { |k, v| v.size > 1 }.map(&:first)

ary.sort.chunk{ |e| e }.select { |e, chunk| chunk.size > 1 }.map(&:first)

И вариант O (N ^ 2) (т.е. менее эффективный):

ary.select{ |e| ary.count(e) > 1 }.uniq

Просто найдите первый экземпляр, где индекс объекта (считая слева) не равен индексу объекта (считая справа).

arr.detect {|e| arr.rindex(e) != arr.index(e) }

Если дубликатов нет, возвращаемое значение будет равно нулю.

Я считаю, что это самое быстрое решение, опубликованное в потоке, также, поскольку оно не основано на создании дополнительных объектов #indexи #rindexреализовано в C. Время выполнения big-O равно N ^ 2 и, следовательно, медленнее, чем Серджио, но время стены может быть намного быстрее из-за того, что «медленные» части работают в C.

detectнаходит только один дубликат. find_allнайду их всех:

a = ["A", "B", "C", "B", "A"]
a.find_all { |e| a.count(e) > 1 }

Вот еще два способа найти дубликат.

Используйте набор

require 'set'

def find_a_dup_using_set(arr)
  s = Set.new
  arr.find { |e| !s.add?(e) }
end

find_a_dup_using_set arr
  #=> "hello" 

Используйте selectвместо, findчтобы вернуть массив всех дубликатов.

использование Array#difference

class Array
  def difference(other)
    h = other.each_with_object(Hash.new(0)) { |e,h| h[e] += 1 }
    reject { |e| h[e] > 0 && h[e] -= 1 }
  end
end

def find_a_dup_using_difference(arr)
  arr.difference(arr.uniq).first
end

find_a_dup_using_difference arr
  #=> "hello" 

Отбросьте, .firstчтобы вернуть массив всех дубликатов.

Оба метода возвращаются, nilесли нет дубликатов.

Я предложилArray#difference добавить его в ядро ​​Ruby. Больше информации в моем ответе здесь .

эталонный тест

Давайте сравним предложенные методы. Для начала нам нужен массив для тестирования:

CAPS = ('AAA'..'ZZZ').to_a.first(10_000)
def test_array(nelements, ndups)
  arr = CAPS[0, nelements-ndups]
  arr = arr.concat(arr[0,ndups]).shuffle
end

и метод для запуска тестов для разных тестовых массивов:

require 'fruity'

def benchmark(nelements, ndups)
  arr = test_array nelements, ndups
  puts "\n#{ndups} duplicates\n"    
  compare(
    Naveed:    -> {arr.detect{|e| arr.count(e) > 1}},
    Sergio:    -> {(arr.inject(Hash.new(0)) {|h,e| h[e] += 1; h}.find {|k,v| v > 1} ||
                     [nil]).first },
    Ryan:      -> {(arr.group_by{|e| e}.find {|k,v| v.size > 1} ||
                     [nil]).first},
    Chris:     -> {arr.detect {|e| arr.rindex(e) != arr.index(e)} },
    Cary_set:  -> {find_a_dup_using_set(arr)},
    Cary_diff: -> {find_a_dup_using_difference(arr)}
  )
end

Я не включил ответ @ JjP, потому что должен быть возвращен только один дубликат, и когда его / ее ответ изменяется, чтобы он соответствовал предыдущему ответу @ Naveed. Я также не включил ответ @ Marin, который, хотя и был опубликован до ответа @ Naveed, возвращал все дубликаты, а не только один (незначительный момент, но нет смысла оценивать оба, так как они идентичны, когда возвращают только один дубликат).

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

Результаты для каждого теста перечислены от самого быстрого до самого медленного:

Сначала предположим, что массив содержит 100 элементов:

benchmark(100, 0)
0 duplicates
Running each test 64 times. Test will take about 2 seconds.
Cary_set is similar to Cary_diff
Cary_diff is similar to Ryan
Ryan is similar to Sergio
Sergio is faster than Chris by 4x ± 1.0
Chris is faster than Naveed by 2x ± 1.0

benchmark(100, 1)
1 duplicates
Running each test 128 times. Test will take about 2 seconds.
Cary_set is similar to Cary_diff
Cary_diff is faster than Ryan by 2x ± 1.0
Ryan is similar to Sergio
Sergio is faster than Chris by 2x ± 1.0
Chris is faster than Naveed by 2x ± 1.0

benchmark(100, 10)
10 duplicates
Running each test 1024 times. Test will take about 3 seconds.
Chris is faster than Naveed by 2x ± 1.0
Naveed is faster than Cary_diff by 2x ± 1.0 (results differ: AAC vs AAF)
Cary_diff is similar to Cary_set
Cary_set is faster than Sergio by 3x ± 1.0 (results differ: AAF vs AAC)
Sergio is similar to Ryan

Теперь рассмотрим массив с 10000 элементов:

benchmark(10000, 0)
0 duplicates
Running each test once. Test will take about 4 minutes.
Ryan is similar to Sergio
Sergio is similar to Cary_set
Cary_set is similar to Cary_diff
Cary_diff is faster than Chris by 400x ± 100.0
Chris is faster than Naveed by 3x ± 0.1

benchmark(10000, 1)
1 duplicates
Running each test once. Test will take about 1 second.
Cary_set is similar to Cary_diff
Cary_diff is similar to Sergio
Sergio is similar to Ryan
Ryan is faster than Chris by 2x ± 1.0
Chris is faster than Naveed by 2x ± 1.0

benchmark(10000, 10)
10 duplicates
Running each test once. Test will take about 11 seconds.
Cary_set is similar to Cary_diff
Cary_diff is faster than Sergio by 3x ± 1.0 (results differ: AAE vs AAA)
Sergio is similar to Ryan
Ryan is faster than Chris by 20x ± 10.0
Chris is faster than Naveed by 3x ± 1.0

benchmark(10000, 100)
100 duplicates
Cary_set is similar to Cary_diff
Cary_diff is faster than Sergio by 11x ± 10.0 (results differ: ADG vs ACL)
Sergio is similar to Ryan
Ryan is similar to Chris
Chris is faster than Naveed by 3x ± 1.0

Обратите внимание, что это find_a_dup_using_difference(arr)было бы намного эффективнее, если бы они Array#differenceбыли реализованы на C, что было бы в случае добавления в ядро ​​Ruby.

Вывод

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

Один очень особый случай, в котором вы можете выбрать решение Криса, будет, если вы захотите использовать метод для раздельного дублирования тысяч небольших массивов и ожидать, что дубликат будет найден, как правило, менее чем в 10 элементах. Это будет немного быстрее поскольку это позволяет избежать небольших дополнительных затрат на создание набора.

Увы большинство ответов O(n^2).

Вот O(n)решение,

a = %w{the quick brown fox jumps over the lazy dog}
h = Hash.new(0)
a.find { |each| (h[each] += 1) == 2 } # => 'the"

В чем сложность этого?

• Бежит O(n)и ломается в первом матче
• Использует O(n)память, но только минимальное количество

Теперь, в зависимости от того, как часто встречаются дубликаты в вашем массиве, время выполнения может стать еще лучше. Например, если размер массива O(n)был выбран из совокупности k << nразличных элементов, становится O(k)сложнее только время выполнения и пространство , однако более вероятно, что исходный плакат проверяет входные данные и хочет убедиться, что нет дубликатов. В этом случае и время выполнения, и сложность памяти, O(n)поскольку мы ожидаем, что элементы не будут иметь повторений для большинства входных данных.

У объектов Ruby Array отличный метод select.

select {|item| block } → new_ary
select → an_enumerator

Первая форма - это то, что вас здесь интересует. Позволяет выбирать объекты, которые проходят тест.

У объектов Ruby Array есть другой метод count.

count → int
count(obj) → int
count { |item| block } → int

В этом случае вас интересуют дубликаты (объекты, которые появляются в массиве более одного раза). Соответствующий тест есть a.count(obj) > 1.

Если a = ["A", "B", "C", "B", "A"]то

a.select{|item| a.count(item) > 1}.uniq
=> ["A", "B"]

Вы заявляете, что хотите только один объект. Так что выбирай один.

find_all () возвращает arrayсодержащий все элементы, enumдля которых blockнет false.

Чтобы получить duplicateэлементы

>> arr = ["A", "B", "C", "B", "A"]
>> arr.find_all { |x| arr.count(x) > 1 }

=> ["A", "B", "B", "A"]

Или дубликаты uniqэлементов

>> arr.find_all { |x| arr.count(x) > 1 }.uniq
=> ["A", "B"] 

Как то так будет работать

arr = ["A", "B", "C", "B", "A"]
arr.inject(Hash.new(0)) { |h,e| h[e] += 1; h }.
    select { |k,v| v > 1 }.
    collect { |x| x.first }

То есть поместите все значения в хеш, где ключ - это элемент массива, а значение - это число вхождений. Затем выберите все элементы, которые встречаются более одного раза. Легко.

Я знаю, что эта тема конкретно о Ruby, но я приземлился здесь в поисках того, как сделать это в контексте Ruby on Rails с ActiveRecord, и подумал, что тоже поделюсь своим решением.

class ActiveRecordClass < ActiveRecord::Base
  #has two columns, a primary key (id) and an email_address (string)
end

ActiveRecordClass.group(:email_address).having("count(*) > 1").count.keys

Вышеприведенное возвращает массив всех адресов электронной почты, которые дублируются в таблице базы данных этого примера (которая в Rails будет "active_record_classes").

a = ["A", "B", "C", "B", "A"]
a.each_with_object(Hash.new(0)) {|i,hash| hash[i] += 1}.select{|_, count| count > 1}.keys

Это O(n)процедура.

В качестве альтернативы вы можете сделать одну из следующих строк. Также O (n), но только одна итерация

a.each_with_object(Hash.new(0).merge dup: []){|x,h| h[:dup] << x if (h[x] += 1) == 2}[:dup]

a.inject(Hash.new(0).merge dup: []){|h,x| h[:dup] << x if (h[x] += 1) == 2;h}[:dup]

Вот мой взгляд на большой набор данных - такой как устаревшая таблица dBase, чтобы найти повторяющиеся части

# Assuming ps is an array of 20000 part numbers & we want to find duplicates
# actually had to it recently.
# having a result hash with part number and number of times part is 
# duplicated is much more convenient in the real world application
# Takes about 6  seconds to run on my data set
# - not too bad for an export script handling 20000 parts

h = {};

# or for readability

h = {} # result hash
ps.select{ |e| 
  ct = ps.count(e) 
  h[e] = ct if ct > 1
}; nil # so that the huge result of select doesn't print in the console

r = [1, 2, 3, 5, 1, 2, 3, 1, 2, 1]

r.group_by(&:itself).map { |k, v| v.size > 1 ? [k] + [v.size] : nil }.compact.sort_by(&:last).map(&:first)

each_with_object твой друг!

input = [:bla,:blubb,:bleh,:bla,:bleh,:bla,:blubb,:brrr]

# to get the counts of the elements in the array:
> input.each_with_object({}){|x,h| h[x] ||= 0; h[x] += 1}
=> {:bla=>3, :blubb=>2, :bleh=>2, :brrr=>1}

# to get only the counts of the non-unique elements in the array:
> input.each_with_object({}){|x,h| h[x] ||= 0; h[x] += 1}.reject{|k,v| v < 2}
=> {:bla=>3, :blubb=>2, :bleh=>2}

Этот код вернет список дублированных значений. Хэш-ключи используются как эффективный способ проверки того, какие значения уже были замечены. В зависимости от того, было ли замечено значение, исходный массив aryразбивается на 2 массива: первый содержит уникальные значения, а второй - дубликаты.

ary = ["hello", "world", "stack", "overflow", "hello", "again"]

hash={}
arr.partition { |v| hash.has_key?(v) ? false : hash[v]=0 }.last.uniq

=> ["hello"]

Вы можете дополнительно сократить его - хотя и за счет немного более сложного синтаксиса - до этой формы:

hash={}
arr.partition { |v| !hash.has_key?(v) && hash[v]=0 }.last.uniq

a = ["A", "B", "C", "B", "A"]
b = a.select {|e| a.count(e) > 1}.uniq
c = a - b
d = b + c

Полученные результаты

 d
=> ["A", "B", "C"]

Если вы сравниваете два разных массива (вместо одного с самим собой), очень быстрый способ - использовать оператор пересечения, &предоставляемый классом Ruby Array .

# Given
a = ['a', 'b', 'c', 'd']
b = ['e', 'f', 'c', 'd']

# Then this...
a & b # => ['c', 'd']

Мне нужно было выяснить, сколько было дубликатов и что они были, поэтому я написал функциональную сборку из того, что Naveed опубликовал ранее:

def print_duplicates(array)
  puts "Array count: #{array.count}"
  map = {}
  total_dups = 0
  array.each do |v|
    map[v] = (map[v] || 0 ) + 1
  end

  map.each do |k, v|
    if v != 1
      puts "#{k} appears #{v} times"
      total_dups += 1
    end
  end
  puts "Total items that are duplicated: #{total_dups}"
end

1. Давайте создадим метод дублирования, который будет принимать массив элементов в качестве входных данных.
2. В теле метода давайте создадим 2 новых объекта массива: один виден, а другой дублирован
3. наконец, давайте переберем каждый объект в данном массиве, и для каждой итерации найдем, что объект существовал в видимом массиве.
4. если объект существовал в seen_array, то он считается дублирующим объектом и помещает этот объект в duplication_array
5. если объект не существует в видимом, то он считается уникальным объектом и помещает этот объект в seen_array

давайте продемонстрируем в реализации кода

def duplication given_array
  seen_objects = []
  duplication_objects = []

  given_array.each do |element|
    duplication_objects << element if seen_objects.include?(element)
    seen_objects << element
  end

  duplication_objects
end

Теперь вызовите метод дублирования и выведите результат возврата -

dup_elements = duplication [1,2,3,4,4,5,6,6]
puts dup_elements.inspect

[1,2,3].uniq!.nil? => true [1,2,3,3].uniq!.nil? => false

Обратите внимание, что вышесказанное является разрушительным