Comment trouver et retourner une valeur dupliquée dans un tableau ?

Question

arr est un tableau de chaînes de caractères :

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

Quel serait un moyen simple et élégant de vérifier si arr a des doublons, et si c'est le cas, retourner l'un d'entre eux (peu importe lequel) ?

Exemples :

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

Answer 1

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

---

Je sais que ce n'est pas une réponse très élégante, mais je l'adore. C'est un beau code en une ligne. Et il fonctionne parfaitement bien, sauf si vous avez besoin de traiter un énorme ensemble de données.

Vous cherchez une solution plus rapide ? C'est ici que ça se passe !

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

Il est linéaire, O(n), mais doit maintenant gérer de multiples lignes de code, a besoin de cas de test, etc.

Si vous avez besoin d'une solution encore plus rapide, essayez plutôt le C.

Et voici l'essentiel de la comparaison des différentes solutions : https://gist.github.com/naveed-ahmad/8f0b926ffccf5fbd206a1cc58ce9743e

Answer 2

Vous pouvez le faire de plusieurs façons, la première étant la plus rapide :

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)

Et une option O(N^2) (c'est-à-dire moins efficace) :

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

Answer 3

Il suffit de trouver le premier cas où l'indice de l'objet (en comptant à partir de la gauche) n'est pas égal à l'indice de l'objet (en comptant à partir de la droite).

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

S'il n'y a pas de doublons, la valeur de retour sera nulle.

Je pense que c'est la solution la plus rapide affichée dans le fil de discussion jusqu'à présent, car elle ne repose pas sur la création d'objets supplémentaires, et #index y #rindex sont implémentés en C. Le temps d'exécution de big-O est N^2 et donc plus lent que celui de Sergio, mais le temps de paroi pourrait être beaucoup plus rapide en raison du fait que les parties "lentes" sont exécutées en C.

Answer 4

detect ne trouve qu'un seul doublon. find_all les trouvera tous :

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

Answer 5

Les objets Ruby Array disposent d'une excellente méthode, select .

select {|item| block }  new_ary
select  an_enumerator

C'est la première forme qui vous intéresse ici. Il vous permet de sélectionner les objets qui passent un test.

Les objets Ruby Array ont une autre méthode, count .

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

Dans ce cas, vous vous intéressez aux doublons (objets qui apparaissent plus d'une fois dans le tableau). Le test approprié est a.count(obj) > 1 .

Si a = ["A", "B", "C", "B", "A"] alors

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

Vous déclarez que vous voulez seulement un objet. Alors choisissez-en un.