Moyen plus élégant de vérifier les doublons dans le tableau C ++?

J'ai écrit ce code en C++ dans le cadre d'un uni tâche où j'en ai besoin pour s'assurer qu'il n'y a pas de doublons dans un tableau:

//Check for duplicate numbers in user inputted data
    int i; //Need to declare i here so that it can be accessed by the 'inner' loop that starts on line 21
    for(i = 0;i < 6; i++) { //Check each other number in the array
        for(int j = i; j < 6; j++) { //Check the rest of the numbers
            if(j != i) { //Makes sure don't check number against itself
                if(userNumbers[i] == userNumbers[j]) {
                    b = true;
                }
            }
            if(b == true) { //If there is a duplicate, change that particular number
                cout << "Please re-enter number " << i + 1 << ". Duplicate numbers are not allowed:" << endl;
                cin >> userNumbers[i];
            }
        } //Comparison loop
        b = false; //Reset the boolean after each number entered has been checked
    } //Main check loop

Il fonctionne parfaitement, mais j'aimerais savoir si il y a plus d'élégance ou de moyen efficace pour vérifier.

source d'informationauteur Saladin Akara

arrays c++duplicates

19

Vous pouvez trier le tableau en O(nlog(n)), alors il suffit de regarder jusqu'à ce que le prochain numéro. Qui est considérablement plus rapide que votre O(n^2) algorithmes existants. Le code est beaucoup plus propre. Votre code n'est pas de garantir l'absence de doublons ont été insérés lorsqu'ils étaient entrés à nouveau. Vous devez éviter les doublons existants, en premier lieu.
```
std::sort(userNumbers.begin(), userNumbers.end());
for(int i = 0; i < userNumbers.size() - 1; i++) {
    if (userNumbers[i] == userNumbers[i + 1]) {
        userNumbers.erase(userNumbers.begin() + i);
        i--;
    }
}
```
J'ai aussi la deuxième reccomendation d'utiliser un std::set - pas de doublons.

La solution suivante est basée sur le tri le nombre, puis en supprimant les doublons:

#include <algorithm>

int main()
{
    int userNumbers[6];

    //...

    int* end = userNumbers + 6;
    std::sort(userNumbers, end);
    bool containsDuplicates = (std::unique(userNumbers, end) != end);
}

En effet, la manière la plus rapide et aussi loin que je peux voir le plus élégant de la méthode est comme conseillé ci-dessus:

std::vector<int> tUserNumbers;
//...
std::set<int> tSet(tUserNumbers.begin(), tUserNumbers.end());
std::vector<int>(tSet.begin(), tSet.end()).swap(tUserNumbers);

Il est O(n log n). Ceci cependant ne pas le faire, si l'ordre des nombres dans le tableau d'entrée doit être maintenu... Dans ce cas j'ai fait:

    std::set<int> tTmp;
    std::vector<int>::iterator tNewEnd = 
        std::remove_if(tUserNumbers.begin(), tUserNumbers.end(), 
        [&tTmp] (int pNumber) -> bool {
            return (!tTmp.insert(pNumber).second);
    });
    tUserNumbers.erase(tNewEnd, tUserNumbers.end());

qui est toujours en O(n log n) et conserve l'original de l'ordre des éléments dans tUserNumbers.

Acclamations,

Paul

6

Vous pouvez ajouter tous les éléments d'un ensemble et de vérifier lors de l'ajout si il est déjà présent ou non. Ce serait plus élégant et efficace.
5

Il est dans le prolongement de la réponse par @Chiot, qui est actuellement la meilleure réponse.

PS : j'ai essayé d'insérer ce message comme commentaire dans l'actuelle meilleure réponse par @Chiot, mais ne pouvait pas, de sorte que je n'ai pas de 50 points encore. Aussi un peu de données expérimentales est partagé ici pour obtenir de l'aide.

À la fois std::set et std::map sont mis en œuvre dans la STL à l'aide Équilibré arbre de Recherche Binaire. Donc, les deux conduisent à une complexité de O(nlogn) uniquement dans ce cas. Alors que la meilleure performance peut être atteint que si une table de hachage est utilisée. std::unordered_map offre table de hachage basée sur la mise en œuvre pour une recherche plus rapide. J'ai testé avec tous les trois de mise en œuvre et les résultats en utilisant std::unordered_map être mieux que les std::set et std::map. Les résultats et le code sont présentées ci-dessous. Les Images sont l'instantané de la performance mesurée par LeetCode sur les solutions.

bool hasDuplicate(vector<int>& nums) { size_t count = nums.size(); if (!count) return false; std::unordered_map<int, int> tbl; //std::set<int> tbl; for (size_t i = 0; i < count; i++) { if (tbl.find(nums[i]) != tbl.end()) return true; tbl[nums[i]] = 1; //tbl.insert(nums[i]); } return false; }

unordered_map de Performance (temps d'Exécution était de 52 ms ici)

Set/Carte Performance

Je ne suis pas sûr de savoir pourquoi cela n'a pas été suggéré, mais ici c'est encore une façon de base est de 10 à rechercher des doublons dans O(n).. Le problème que je vois avec la déjà suggéré O(n) solution est qu'elle nécessite que les chiffres seront triés en premier lieu.. Cette méthode est O(n) et ne nécessite pas le jeu d'être triés. Le truc cool, c'est que la vérification si un chiffre a des doublons est O(1). Je sais que ce fil est probablement mort, mais peut-être que ça va aider quelqu'un! 🙂

/*
============================
Foo
============================
* 
   Takes in a read only unsigned int. A table is created to store counters 
   for each digit. If any digit's counter is flipped higher than 1, function
   returns. For example, with 48778584:
    0   1   2   3   4   5   6   7   8   9
   [0] [0] [0] [0] [2] [1] [0] [2] [2] [0]

   When we iterate over this array, we find that 4 is duplicated and immediately
   return false.

*/
bool Foo( unsigned const int &number)
{
    int temp = number;
    int digitTable[10]={0};

    while(temp > 0)
    {
        digitTable[temp % 10]++; //Last digit's respective index.
        temp /= 10; //Move to next digit
    }

    for (int i=0; i < 10; i++)
    {
        if (digitTable [i] > 1)
        {
            return false;
        }
    }
    return true;
}

3

C'est ok, spécialement pour les petites matrice des longueurs. Je ne l'utiliserais plus efficace aproaches (moins de n^2/2 comparaisons) si le tableau est mugh grand de voir DeadMG de réponse.

Quelques petites corrections pour votre code:
- Au lieu de int j = i écrireint j = i +1 et vous pouvez les omettre de votre if(j != i) test
- Vous devriez pas besoin de déclarer i variable en dehors de la for déclaration.

//std::unique(_copy) requires a sorted container.
std::sort(cont.begin(), cont.end());

//testing if cont has duplicates
std::unique(cont.begin(), cont.end()) != cont.end();

//getting a new container with no duplicates
std::unique_copy(cont.begin(), cont.end(), std::back_inserter(cont2));

#include<iostream>
#include<algorithm>

int main(){

    int arr[] = {3, 2, 3, 4, 1, 5, 5, 5};
    int len = sizeof(arr) / sizeof(*arr); //Finding length of array

    std::sort(arr, arr+len);

    int unique_elements = std::unique(arr, arr+len) - arr;

    if(unique_elements == len) std::cout << "Duplicate number is not present here\n";
    else std::cout << "Duplicate number present in this array\n";

    return 0;
}

Vous devez vous connecter pour publier un commentaire.