trouver la répétition des numéros en double

Question

ceci est mon algorithme que je l'ai écrit avec mes amis (qui sont dans le site stackoverflow) cet algorithme trouve que le premier numéro de double et retourne patchage œuvres dans O(n) Je veux compléter cet algorithme qui m'aide à obtenir des numéros en double avec leur répétition. considère que j'ai [1,1,3,0,5,1,5] Je veux cet algorithme pour retourner 2 numéros en double qui sont 1 and 5 avec leur répétition qui est 3 and 2 respectivement. comment puis-je faire cela avec O(n)?

1 Algorithm Duplicate(arr[1:n],n) 
2 
3 { 
4  Set s = new HashSet();i:=0; 
5  while i<a.size() do 
6  { 
7   if(!s.add(a[i)) then 
8   { 
9    return a[i]; //this is a duplicate value! 
10   break; 
11   } 
12   i++; 
13  } 
14 } 

Answer 1

Vous pouvez le faire en Java:

List<Integer> num=Arrays.asList(1,1,1,2,3,3,4,5,5,5); 
    Map<Integer,Integer> countNum=new HashMap<Integer, Integer>(); 
    for(int n:num) 
    { 
     Integer nu; 
     if((nu=countNum.get(n))==null) 
     { 
      countNum.put(n,1); 
      continue; 
     } 
     countNum.put(n,nu+1); 
    } 

Au lieu de itérer chaque fois pour obtenir le nombre de dupliquer il est préférable de stocker le compte sur la carte.

Answer 2

1. Utilisez une carte/structure de données dictionnaire.
2. Itérer sur la liste.
3. Pour chaque élément de la liste, effectuez une recherche de carte. Si la clé (élément) existe, augmentez sa valeur. Si la clé n'existe pas, insérez la clé et le nombre initial.

Answer 3

Dans ce cas particulier, il ne s'agit pas de l'algorithme, mais de la structure de données: Multiset est comme un Set, sauf qu'il ne stocke pas seulement des éléments uniques, mais il stocke le nombre de fois que chaque élément est dans le Multiset. Fondamentalement, un Set vous indique si un élément particulier est dans le Setdu tout, un Multiset en plus vous indique également la fréquence ce point particulier est dans le Multiset. Donc, tout ce que vous avez à faire est de construire un Multiset à partir de Array. Voici un exemple dans Ruby:

require 'multiset' 

print Multiset[1,1,3,0,5,1,5] 

Oui, c'est tout ce qu'il y a à faire. Cette impression:

#3 1 
#1 3 
#1 0 
#2 5 

Si vous ne souhaitez que des doublons réels, il vous suffit delete ces éléments avec un nombre inférieur à 2:

print Multiset[1,1,3,0,5,1,5].delete_with {|item, count| count < 2 } 

Cette impression juste

#1 3 
#2 5 

Comme @suihock mentionne , vous pouvez également utiliser un Map, ce qui signifie simplement qu'au lieu de Multiset prendre soin de l'élément comptant pour vous, vous devez le faire vous-même:

m = [1,1,3,0,5,1,5].reduce(Hash.new(0)) {|map, item| map.tap { map[item] += 1 }} 
print m 
# { 1 => 3, 3 => 1, 0 => 1, 5 => 2 } 

Encore une fois, si vous voulez seulement les doublons:

print m.select {|item, count| count > 1 } 
# { 1 => 3, 5 => 2 } 

Mais vous pouvez avoir ce plus facile si au lieu de vous compter, vous utilisez Enumerable#group_by pour regrouper les éléments par eux-mêmes et ensuite cartographier les groupements à leurs tailles.Enfin, reconvertir une Hash:

print Hash[[1,1,3,0,5,1,5].group_by(&->x{x}).map {|n, ns| [n, ns.size] }] 
# { 1 => 3, 3 => 1, 0 => 1, 5 => 2 } 

Tous ces éléments ont une complexité étape du pire amorti Θ (n).