Un modo più elegante di controllare i duplicati nell'array C++?

Question

ho scritto questo codice in C++ come parte di un compito uni in cui ho bisogno per garantire che non vi siano duplicati all'interno di un array:

// 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 

Funziona perfettamente, ma mi piacerebbe sapere se c'è un modo più elegante o efficiente per controllare.

Answer 1

È possibile ordinare l'array in O (nlog (n)), quindi cercare semplicemente il numero successivo. Questo è sostanzialmente più veloce dell'algoritmo O (n^2) esistente. Il codice è anche molto più pulito. Il tuo codice inoltre non garantisce che non siano stati inseriti duplicati quando sono stati reinseriti. È necessario evitare che i duplicati esistano in primo luogo.

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--; 
    } 
} 

Ho anche la seconda raccomandazione di utilizzare un std :: set - nessun duplicato lì.

Answer 2

È possibile aggiungere tutti gli elementi in un set e controllare quando si aggiunge se è già presente o meno. Sarebbe più elegante ed efficiente.

Answer 3

Va bene, specialmente per le lunghezze di array di piccole dimensioni. Userei gli aproach più efficienti (meno di n^2/2 confronti) se l'array è più grande - vedi la risposta di DeadMG.

Alcune piccole correzioni per il tuo codice:

• Invece di int j = i scrittura int j = i +1 e si può omettere il test if(j != i)
• È should't necessario dichiarare i variabile fuori la dichiarazione for.

Answer 4

In effetti, il più veloce e, per quanto posso vedere più elegante metodo è come consigliato sopra:

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

Si tratta di O (n log n). Questo però non lo rende, se l'ordinamento dei numeri nella matrice di input deve essere mantenuto ... In questo caso ho fatto:

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()); 

che è ancora O (n log n) e mantiene l'originale ordinamento di elementi in tUserNumbers.

Cheers,

Paul

Answer 5

la seguente soluzione si basa su l'ordinamento dei numeri e poi rimuovere i duplicati:

#include <algorithm> 

int main() 
{ 
    int userNumbers[6]; 

    // ... 

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

Answer 6

//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)); 

Answer 7

non sono sicuro perché questo non ha è stato suggerito ma ecco un modo nella base 10 per trovare i duplicati in O (n). Il problema che vedo con la soluzione O (n) già suggerita è che richiede che le cifre siano ordinate per prime .. Questo metodo è O (n) e non richiede che il set sia ordinato. La cosa interessante è che controllare se una cifra specifica ha duplicati è O (1). So che questo thread probabilmente è morto ma forse aiuterà qualcuno! :)

/* 
============================ 
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; 
} 

Answer 8

È in estensione alla risposta di @Puppy, che è la migliore risposta corrente.

PS: ho cercato di inserire questo post come commento nella risposta migliore corrente da @Puppy ma non è stato possibile perché non ho ancora 50 punti. Anche un po 'di dati sperimentali è condiviso qui per ulteriore aiuto.

Entrambi std :: set e std :: map sono implementati in STL utilizzando solo la struttura di ricerca binaria bilanciata. Quindi entrambi determineranno una complessità di O (nlogn) solo in questo caso. Mentre è possibile ottenere prestazioni migliori se si utilizza una tabella hash. std :: unordered_map offre un'implementazione basata sulla tabella hash per una ricerca più rapida. Ho sperimentato tutte e tre le implementazioni e ho trovato i risultati usando std :: unordered_map per essere migliore di std :: set e std :: map. Risultati e codice sono condivisi di seguito. Le immagini sono l'istantanea delle prestazioni misurate da LeetCode sulle soluzioni.

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 Performance (Tempo di esecuzione è di 52 ms qui)

Set/Mappa prestazioni

Answer 9

#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; 
}