Como encontrar e retornar um valor duplicado na matriz

arr é uma matriz de strings:

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

Qual seria uma maneira fácil e elegante de verificar se arrhá duplicatas e, em caso afirmativo, retornar uma delas (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 }

Sei que não é uma resposta muito elegante, mas adoro. É um código liner bonito. E funciona perfeitamente bem, a menos que você precise processar um enorme conjunto de dados.

Procurando uma solução mais rápida? Aqui está!

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

É linear, O (n), mas agora precisa gerenciar várias linhas de código, precisa de casos de teste etc.

Se você precisar de uma solução ainda mais rápida, talvez tente C.

E aqui está a essência comparando diferentes soluções: https://gist.github.com/naveed-ahmad/8f0b926ffccf5fbd206a1cc58ce9743e

Você pode fazer isso de várias maneiras, sendo a primeira opção 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 objeto (contando da esquerda) não é igual ao índice do objeto (contando da direita).

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

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

Eu acredito que esta é a solução mais rápida postada no thread até agora também, já que não depende da criação de objetos adicionais #indexe #rindexé implementada em C. O tempo de execução do big-O é N ^ 2 e, portanto, mais lento que Sergio, mas o tempo de parede pode ser muito mais rápido devido ao fato de as partes "lentas" rodarem em C.

detectencontra apenas uma duplicata. find_allencontrará 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 selectno lugar de findpara retornar uma matriz de todas as duplicatas.

Usar 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 .firstpara retornar uma matriz de todas as duplicatas.

Ambos os métodos retornam nilse não houver duplicatas.

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

Referência

Vamos comparar os métodos sugeridos. Primeiro, precisamos de uma matriz 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_difference(arr)}
  )
end

Não incluí a resposta de @ JjP porque apenas uma duplicata deve ser retornada e, quando sua resposta é modificada para fazer isso, é igual à resposta anterior de @ Naveed. Também não incluí a resposta de @ Marin, que, embora postada antes da resposta de @ Naveed, retornava todas as duplicatas em vez de apenas uma (um ponto menor, mas não faz sentido avaliar as duas, 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 que não deveriam ter nenhum efeito sobre o desempenho, pois calculavam todas as duplicatas antes de selecionar uma.

Os resultados de cada benchmark estão listados do mais rápido ao mais lento:

Primeiro, suponha que a matriz 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

Observe que find_a_dup_using_difference(arr)seria muito mais eficiente se Array#differencefosse implementado em C, o que seria o caso se fosse adicionado ao núcleo do Ruby.

Conclusão

Muitas das respostas são razoáveis, mas usar um Conjunto é a melhor opção . É o mais rápido nos casos médios, o mais rápido nos casos mais difíceis e apenas nos casos computacionalmente triviais - quando sua escolha não importa de qualquer maneira - pode ser derrotado.

O único caso muito especial em que você pode escolher a solução de Chris seria se você deseja usar o método para desduplicar separadamente milhares de arrays pequenos e esperar encontrar um duplicado normalmente com menos de 10 itens. Isso será um pouco mais rápido pois evita a pequena sobrecarga adicional de criar o conjunto.

Infelizmente, a maioria das respostas são O(n^2).

Aqui está uma O(n)solução,

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 O(n)e quebra na primeira partida
• Usa O(n)memória, mas apenas a quantidade mínima

Agora, dependendo da frequência de duplicatas em sua matriz, esses tempos de execução podem se tornar ainda melhores. Por exemplo, se a matriz de tamanho O(n)tiver sido amostrada de uma população de k << nelementos diferentes, apenas a complexidade do tempo de execução e do espaço se tornará O(k); no entanto, é mais provável que o pôster original esteja validando a entrada e queira garantir que não haja duplicatas. Nesse caso, o tempo de execução e a complexidade da memória, O(n)pois esperamos que os elementos não tenham repetições para a maioria das entradas.

Os objetos Ruby Array têm um ótimo método select,.

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

A primeira forma é o que lhe interessa aqui. Permite selecionar objetos que passam no teste.

Os objetos Ruby Array possuem outro método count,.

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

Nesse caso, você está interessado em duplicatas (objetos 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 deseja apenas um objeto. Então escolha um.

find_all () retorna um arraycontendo todos os elementos dos enumquais blocknão éfalse .

Para obter duplicateelementos

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

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

Ou duplicar uniqelementos

>> 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, onde key é o elemento da matriz e value é o número de ocorrências. Em seguida, selecione todos os elementos que ocorrem mais de uma vez. Fácil.

Eu sei que esse tópico é sobre Ruby especificamente, mas 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 exemplo acima retorna uma matriz de todos os endereços de email duplicados na tabela de banco de dados deste exemplo (que no Rails seria "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

Este é um O(n)procedimento.

Como alternativa, você pode executar 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]

Aqui está minha opinião sobre um grande conjunto de dados - 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}

Este código retornará uma lista de valores duplicados. As chaves de hash são usadas como uma maneira eficiente de verificar quais valores já foram vistos. Com base em se o valor foi visto, a matriz original aryé particionada em 2 matrizes: primeiro contendo valores exclusivos e segundo contendo duplicatas.

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

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

=> ["hello"]

Você pode reduzi-lo ainda mais - embora a um custo de sintaxe um pouco mais complexa - para este formato:

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

Resultados

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

Se você estiver comparando duas matrizes diferentes (em vez de uma contra ela mesma), uma maneira muito rápida é usar o operador de interseção &fornecido pela classe Ruby Array .

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

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

Eu precisava descobrir quantas duplicatas havia e o que eram, então escrevi uma função baseada no que Naveed havia publicado anteriormente:

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. Vamos criar um método de duplicação que use matriz de elementos como entrada
2. No corpo do método, vamos criar 2 novos objetos de matriz, um é visto e outro é duplicado
3. finalmente, vamos iterar através de cada objeto em uma matriz especificada e, para cada iteração, descobrimos que o objeto existia na matriz vista.
4. se o objeto existir na matriz seen_array, será considerado como objeto duplicado e enviará o objeto para duplication_array
5. se o objeto não existir no visto, ele será considerado um objeto exclusivo e enviará o objeto para a matriz seen_array

vamos demonstrar na implementação de código

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

Agora chame o método de duplicação e o resultado do retorno de saída -

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

Observe que o acima é destrutivo