Ruby: Como encontrar e retornar um valor duplicado na matriz?

arr é um array de strings, por exemplo: ["hello", "world", "stack", "overflow", "hello", "again"] .

O que seria maneira fácil e elegante para verificar se arr tem duplicatas, e se sim, retorne um deles (não importa qual).

Exemplos:

 ["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 } 

Você pode fazer isso de algumas maneiras, com a primeira opção sendo a mais rápida:

 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) 

E uma opção O (N ^ 2) (ou seja, menos eficiente):

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

Basta encontrar a primeira instância em que o índice do object (contando a partir da esquerda) não é igual ao índice do object (contando a partir da direita).

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

Se não houver duplicatas, o valor de retorno será nulo.

Acredito que essa também seja a solução mais rápida postada no segmento até agora, já que não depende da criação de objects adicionais, e #index e #rindex são implementados em C. O tempo de execução big-O é N ^ 2 e assim mais lento que o de Sergio, mas o tempo de parede poderia ser muito mais rápido devido ao fato de que as partes “lentas” correm em C.

detect apenas encontra um duplicado. find_all encontrará todos eles:

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

Aqui estão mais duas maneiras de encontrar uma duplicata.

Use um conjunto

 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" 

Use select no lugar de find para retornar uma matriz de todos os duplicados.

Use 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" 

Solte primeiro para retornar uma matriz de todas as duplicatas.

Ambos os methods retornam nil se não houver duplicatas.

Eu propus que Array#difference fosse adicionada ao núcleo do Ruby. Mais informações estão na minha resposta aqui .

Referência

Vamos comparar os methods sugeridos. Primeiro, precisamos de um array para testar:

 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 

e um método para executar os benchmarks para diferentes matrizes de teste:

 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_set(arr)} ) end 

Eu não incluí a resposta do @JjP porque apenas uma duplicata deve ser retornada, e quando sua resposta é modificada para fazer isso é a mesma que a resposta anterior do @ Naveed. Também não incluí a resposta de @ Marin, que, enquanto postada antes da resposta de @ Naveed, retornou todas as duplicatas em vez de apenas uma (um ponto menor, mas não há sentido em avaliar ambas, pois são idênticas quando retornam apenas uma duplicata).

Também modifiquei outras respostas que retornaram todas as duplicatas para retornar apenas a primeira encontrada, mas isso não deve ter efeito algum sobre o desempenho, já que elas computaram todas as duplicatas antes de selecionar uma.

Suponha primeiro que o array contenha 100 elementos:

 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 

Agora considere uma matriz com 10.000 elementos:

 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 

Note que find_a_dup_using_difference(arr) seria muito mais eficiente se Array#difference fosse implementada em C, o que seria o caso se fosse adicionado ao núcleo Ruby.

Objetos Ruby Array tem um ótimo método, select .

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

A primeira forma é o que te interessa aqui. Ele permite que você selecione objects que passam por um teste.

Objetos Ruby Array possuem outro método, count .

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

Nesse caso, você está interessado em duplicatas (objects que aparecem mais de uma vez na matriz). O teste apropriado é a.count(obj) > 1 .

Se a = ["A", "B", "C", "B", "A"] , então

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

Você afirma que você quer apenas um object. Então escolha um.

Infelizmente, a maioria das respostas é O(n^2) .

Aqui está uma solução 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" 

Qual é a complexidade disso?

  • Corre em O(n) e quebra no primeiro jogo
  • Usa O(n) memory, mas apenas a quantidade mínima

Agora, dependendo de como as duplicatas são frequentes em sua matriz, esses tempos de execução podem se tornar ainda melhores. Por exemplo, se a matriz de tamanho O(n) foi amostrada de uma população de k < < n diferentes elementos, apenas a complexidade para tempo de execução e espaço se torna O(k) , no entanto, é mais provável que o pôster original esteja validando input e quer ter certeza de que não há duplicatas. Nesse caso, tanto tempo de execução quanto complexidade de memory O(n) já que esperamos que os elementos não tenham repetições para a maioria das inputs.

Eu sei que este tópico é sobre Ruby especificamente, mas eu cheguei aqui procurando como fazer isso dentro do contexto do Ruby on Rails com o ActiveRecord e pensei em compartilhar minha solução também.

 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 

O acima retorna uma matriz de todos os endereços de e-mail duplicados na tabela de database deste exemplo (que no Rails seria “active_record_classs”).

find_all () retorna uma array contendo todos os elementos de enum para os quais o block não é false .

Para obter elementos duplicate

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

Ou duplicar elementos uniq

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

Algo assim vai funcionar

 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 } 

Ou seja, coloque todos os valores em um hash em que key é o elemento de array e value é o número de ocorrências. Em seguida, selecione todos os elementos que ocorrem mais de uma vez. Fácil.

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

Este é um procedimento O(n) .

Alternativamente, você pode fazer uma das seguintes linhas. Também O (n) mas apenas uma iteração

 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] 

Se você está comparando duas matrizes diferentes (ao invés de uma contra si mesma), uma maneira muito rápida é usar o operador de intersecção & fornecido pela class Array do Ruby .

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

Aqui está minha opinião sobre um grande dataset – como uma tabela legada do dBase para encontrar partes duplicadas

 # 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 é seu amigo!

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

Resultados

  d => ["A", "B", "C"] 
 def firstRepeatedWord(string) h_data = Hash.new(0) string.split(" ").each{|x| h_data[x] +=1} h_data.key(h_data.values.max) end 

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

Observe o acima é destrutivo