Algorithme pour trouver le double des nombres dans un tableau ---la Façon la plus Rapide

J'ai besoin de la manière la plus rapide et simple de l'algorithme qui trouve le double des nombres dans un tableau, devraient également être en mesure de connaître le nombre de doublons.

Par exemple: si le tableau est {2,3,4,5,2,4,6,2,4,7,3,8,2}

Je devrais être en mesure de savoir qu'il y a quatre 2, deux de 3 et de trois 4.

Le plus souvent, le plus rapide de l'algorithme ne sera pas simple et la plus simple de ne pas être rapide 🙁
L'algorithme le plus rapide est de l'écrire vous-même 🙂
Quelle est la spécification d'entrée? De petits nombres naturels? Tout non signé de 32 bits des nombres? Des centaines de personnes? Des centaines de millions?

OriginalL'auteur Raviteja | 2009-12-05

algorithm c

3

Faire une table de hachage dont la clé est la matrice de l'élément et la valeur est contre combien de fois le tableau correspondant de l'élément a eu lieu dans la gamme. C'est efficace pour le faire, mais probablement pas le moyen le plus rapide.

Quelque chose comme ceci (en pseudo-code). Vous trouver beaucoup de hachage carte des implémentations de C par googler.
```
 hash_map = create_new_hash_map()
 for item in array {
   if hash_map.contains_key(item){
      counter = hash_map.get(item)
   } else {
      counter = 0
   }
   counter = counter + 1
   hash_map.put(item, counter)
 }
```
OriginalL'auteur Juha Syrjälä
3

Cela peut être résolu avec élégance à l'aide de Linq:
```
public static void Main(string[] args)
{
    List<int> list = new List<int> { 2, 3, 4, 5, 2, 4, 6, 2, 4, 7, 3, 8, 2 };

    var grouping = list
        .GroupBy(x => x)
        .Select(x => new { Item = x.Key, Count = x.Count()});

    foreach (var item in grouping)
        Console.WriteLine("Item {0} has count {1}", item.Item, item.Count);
}
```
En interne, il utilise probablement le hachage de la partition de la liste, mais le code se cache à l'intérieur les détails ici, nous sommes seulement dire ce à calculer. Le compilateur /runtime est libre de choisir comment calculer et optimiser comme il l'entend. Grâce à Linq ce même code sera exécuté de manière efficace si l'exécution d'une liste en mémoire, ou si la liste est dans une base de données. Dans le code réel, vous devez utiliser, mais je suppose que vous voulez savoir comment faire en interne, il travaille.

Plus impératif approche qui démontre le réel de l'algorithme est le suivant:
```
    List<int> list = new List<int> { 2, 3, 4, 5, 2, 4, 6, 2, 4, 7, 3, 8, 2 };

    Dictionary<int, int> counts = new Dictionary<int, int>();
    foreach (int item in list)
    {
        if (!counts.ContainsKey(item))
        {
            counts[item] = 1;
        }
        else
        {
            counts[item]++;
        }
    }

    foreach (KeyValuePair<int, int> item in counts)
        Console.WriteLine("Item {0} has count {1}", item.Key, item.Value);
```
Ici, vous pouvez voir que nous itérer sur la liste qu'une seule fois, en gardant le nombre de chaque élément nous voir sur le chemin. Ce serait une mauvaise idée si les éléments ont été dans une base de données, donc pour de vrai code, préfèrent utiliser la méthode Linq.

Il dit qu'il a besoin de l'algorithme en C
La question, maintenant, dit le C comme langage.
OK merci. C n'a pas de Linq, vous devez utiliser la deuxième méthode.
Je vais laisser le traduire en C comme un exercice pour le lecteur. 🙂

OriginalL'auteur Mark Byers
3

voici une version en C qui le fait, avec l'entrée standard; il est aussi rapide que la longueur de l'entrée (attention, le nombre de paramètres sur la ligne de commande est limitée...), mais devrait vous donner une idée sur comment procéder:
```
#include <stdio.h>

int main ( int argc, char **argv ) {
    int dups[10] = { 0 };
    int i;

    for ( i = 1 ; i < argc ; i++ ) 
        dups[atoi(argv[i])]++;

    for ( i = 0 ; i < 10 ; i++ )
        printf("%d: %d\n", i, dups[i]);

    return 0;
}
```
exemple d'utilisation:
```
    $ gcc -o dups dups.c

    $ ./dups 0 0 3 4 5
0: 2
1: 0
2: 0
3: 1
4: 1
5: 1
6: 0
7: 0
8: 0
9: 0
```
mises en garde:
- si vous prévoyez de compter aussi le nombre de 10s, 11s, et ainsi de suite -> dup tableau[] doit être plus grand
- laissé comme exercice est de mettre en œuvre la lecture à partir d'un tableau d'entiers et de déterminer leur position
ne postez pas dangereuse en soi un exemple de code tel qu'il sera lu par des personnes sans grande expérience de la programmation; le moins que vous devez faire est de paramétrer la valeur max (par exemple #define MAX_VALUE 10) et vérifier que l'entrée est >= 0 et < MAX_VALUE pour éviter les dépassements de la mémoire tampon; par exemple, le code, un simple assert() serait suffisant; à l'aide de strtoul() bien valider la saisie de l'utilisateur serait un bonus
mon intention était de lui faire effectuer les vérifications tant que réfléchir à la manière de compter au-delà de 10 éléments différents. L'exercice des odeurs trop de devoirs à la maison pour donner une solution complète.

OriginalL'auteur lorenzog
2

Si vous connaissez les limites inférieure et supérieure, et ils ne sont pas trop éloignés, ce serait un bon endroit pour utiliser un Tri Radix. Depuis cette odeur de devoirs, je pars à l'OP pour lire l'article et de mettre en œuvre l'algorithme.

OriginalL'auteur Stephen C
2

Plus vous nous dire à propos de l'entrée des tableaux les plus rapides, nous pouvons faire de l'algorithme. Par exemple, pour votre exemple de nombres à un chiffre, puis la création d'un tableau de 10 éléments (indexée 0:9) et l'accumulation d'un certain nombre d'occurrences de nombre dans le droit de l'élément du tableau à (mal formulé explication, mais vous avez probablement vous attrapez ma dérive) est susceptible d'être plus rapide que le hachage. (Je dis probablement à être plus rapide car je n'ai pas fait de mesures et ne veut pas).

Je suis d'accord avec la plupart des répondants que le hachage est probablement la bonne approche pour le cas le plus général, mais il est toujours utile de réfléchir à savoir si le vôtre est un cas spécial.

OriginalL'auteur High Performance Mark
1

Si vous ne souhaitez pas utiliser la table de hachage ou smtg comme ça, juste trier le tableau puis de compter le nombre d'occurrences, quelque chose comme ci-dessous devrait fonctionner
```
    Arrays.sort(array);
    lastOne=array's first element;
    count=0,
    for(i=0; i <array's length; i++)
    {
        if(array[i]==lastOne)
            increment count
        else        
            print(array[i] + " has " + count + " occurrences");
            lastOne=array[i+1];
    }
```
+1 pour une idée simple que dans le cas, vous pouvez modifier le tableau n'a pas besoin de beaucoup plus de mémoire lorsque les éléments ne sont pas répétées fréquemment comme nous avons avec la table de hachage approche.

OriginalL'auteur erdemoo
1

Si la plage de numéros est connu et les petits, vous pouvez utiliser un tableau pour garder une trace de combien de fois vous avez vu (c'est un seau de tri dans l'essence). SI elle est grande, vous pouvez les trier puis de compter les doublons comme ils le seront suivant les uns des autres.

OriginalL'auteur rmn
1

Vous pouvez utiliser les tables de hachage pour stocker chaque valeur d'élément de clé. Puis ajouter un +1 à chaque fois qu'une clé existe déjà.

OriginalL'auteur Y_Y
0

À l'aide de tables de hachage /tableaux associatifs /dictionnaires (tous la même chose, mais les modifications de terminologie entre les environnements de programmation) est le chemin à parcourir.

Comme un exemple en python:
```
numberList = [1, 2, 3, 2, 1, ...]
countDict = {}
for value in numberList:
    countDict[value] = countDict.get(value, 0) + 1

# Now countDict contains each value pointing to their count
```
Constructions similaires existent dans la plupart des langages de programmation.

OriginalL'auteur Gabriel Reid

> I need the fastest and simple algorithm which finds the duplicate numbers in an array, also should be able to know the number of duplicates.

Je pense que l'algorithme le plus rapide est à compter les doublons dans un tableau:

#include <stdlib.h> 
#include <stdio.h> 
#include <limits.h> 
#include <assert.h> 
typedef int arr_t;
typedef unsigned char dup_t;
const dup_t dup_t_max=UCHAR_MAX;
dup_t *count_duplicates( arr_t *arr, arr_t min, arr_t max, size_t arr_len ){
assert( min <= max );
dup_t *dup = calloc( max-min+1, sizeof(dup[0]) );
for( size_t i=0; i<arr_len; i++ ){
assert( min <= arr[i] && arr[i] <= max && dup[ arr[i]-min ] < dup_t_max );
dup[ arr[i]-min ]++;
}
return dup;
}
int main(void){
arr_t arr[] = {2,3,4,5,2,4,6,2,4,7,3,8,2};
size_t arr_len = sizeof(arr)/sizeof(arr[0]);
arr_t min=0, max=16;
dup_t *dup = count_duplicates( arr, min, max, arr_len );
printf( "  value count\n" );
printf( "  -----------\n" );
for( size_t i=0; i<(size_t)(max-min+1); i++ ){
if( dup[i] ){
printf( "%5i %5i\n", (int)(i+min), (int)(dup[i]) );
}
}
free(dup);
}

Remarque: Vous ne pouvez pas utiliser l'algorithme le plus rapide sur tous les tableaux.

OriginalL'auteur sambowry

Le premier code trie le tableau, puis déplace des éléments uniques à l'avant, en gardant une trace du nombre d'éléments. Il est plus lent que d'utiliser seau de tri, mais aussi plus pratique.

#include <stdio.h>
#include <stdlib.h>
static int cmpi(const void *p1, const void *p2)
{
int i1 = *(const int *)p1;
int i2 = *(const int *)p2;
return (i1 > i2) - (i1 < i2);
}
size_t make_unique(int values[], size_t count, size_t *occ_nums)
{
if(!count) return 0;
qsort(values, count, sizeof *values, cmpi);
size_t top = 0;
int prev_value = values[0];
if(occ_nums) occ_nums[0] = 1;
size_t i = 1;
for(; i < count; ++i)
{
if(values[i] != prev_value)
{
++top;
values[top] = prev_value = values[i];
if(occ_nums) occ_nums[top] = 1;
}
else ++occ_nums[top];
}
return top + 1;
}
int main(void)
{
int values[] = { 2, 3, 4, 5, 2, 4, 6, 2, 4, 7, 3, 8, 2 };
size_t occ_nums[sizeof values / sizeof *values];
size_t unique_count = make_unique(
values, sizeof values / sizeof *values, occ_nums);
size_t i = 0;
for(; i < unique_count; ++i)
{
printf("number %i occurred %u time%s\n",
values[i], (unsigned)occ_nums[i], occ_nums[i] > 1 ? "s": "");
}
}

OriginalL'auteur Christoph

0

option 1: hash.
option 2: trier et compter ensuite des séries consécutives.

OriginalL'auteur Southern Hospitality
0

Il y a un "algorithme" que j'utilise tout le temps pour trouver des doublons de lignes dans un fichier sous Unix:
```
sort file | uniq -d
```
Si vous mettez en œuvre la même stratégie dans C, alors il est très difficile de le battre avec un amateur de stratégie, tels que les tables de hachage. Appel d'un algorithme de tri, puis composez votre propre fonction pour détecter les doublons dans la liste triée. L'algorithme de tri prend O(n*log(n)) du temps et de l'uniq fonction prend un temps linéaire. (De l'Hospitalité du sud fait une remarque similaire, mais je tiens à souligner que ce qu'il appelle "option 2" semble à la fois plus simple et plus rapide que le plus populaire des tables de hachage suggestion.)

OriginalL'auteur Greg Kuperberg
0

De comptage, le tri est la réponse à la question ci-dessus.Si vous voyez l'algorithme de comptage, de tri, vous trouverez qu'il y a un tableau qui est conservé pour garder le comte d'un élément que je présente dans le tableau d'origine.

OriginalL'auteur Soumajyoti
0

Ici est une autre solution mais il faut O(nlogn).
L'utilisation de Diviser et Conquérir approche pour trier le tableau à l'aide de fusion de tri.
Au cours de combiner l'étape de fusion de trier, rechercher les doublons en comparant les éléments dans les deux triés sous-tableaux.

OriginalL'auteur sundar

Vous devez vous connecter pour publier un commentaire.