Bardziej elegancki sposób na sprawdzenie duplikatów w tablicy C++?

Question

Napisałem ten kod w C++ jako część zadania uni gdzie potrzebne, aby zapewnić, że nie ma duplikatów w tablicy:

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

To działa doskonale, ale chciałbym wiedzieć, czy istnieje bardziej elegancki lub skuteczny sposób sprawdzania.

Answer 1

Można sortować tablicę w O (nlog (n)), a następnie po prostu patrzeć do następnego numeru. Jest to znacznie szybsze niż Twój istniejący algorytm O (n^2). Kod jest również o wiele czystszy. Twój kod nie gwarantuje również, że nie włożono duplikatów, gdy zostały ponownie wprowadzone. Musisz przede wszystkim zapobiegać istnieniu duplikatów.

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

Po drugie polecam również użycie std :: set - nie ma tam duplikatów.

Answer 2

Możesz dodać wszystkie elementy do zestawu i sprawdzić przy dodawaniu, czy jest już obecny, czy nie. To byłoby bardziej eleganckie i wydajne.

Answer 3

Jest ok, specjalnie dla małych długości matrycy. Użyłbym bardziej wydajnych aproachów (mniej niż n^2/2 porównań), jeśli macierz jest większa - patrz odpowiedź DeadMG.

Niektóre małe korekty kodu:

• Zamiast int j = i zapisu int j = i +1 i można pominąć nasz test if(j != i)
• should't trzeba zadeklarować zmienną poza i rachunku for.

Answer 4

Rzeczywiście, najszybszy i jak daleko mogę zobaczyć najbardziej elegancki sposób jest zgodnie z zaleceniami powyżej:

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

Jest to O (n log n). To jednak nie czyni go, jeśli kolejność liczb w tablicy wejście musi być utrzymywane ... W tym przypadku robiłam:

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

która nadal jest O (n log n) i utrzymuje oryginał zamawianie elementów w tUserNumbers.

Cheers,

Paul

Answer 5

Poniższy Rozwiązanie oparte jest na sortowanie liczb, a następnie usuwanie duplikatów:

#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

Nie jestem pewien, dlaczego ten nie ma zostały zasugerowane, ale tutaj jest sposób w bazie 10, aby znaleźć duplikaty w O (n). Problem, który widzę z już sugerowanym rozwiązaniem O (n), polega na tym, że wymaga on najpierw posortowania cyfr. Ta metoda to O (n) i nie wymaga sortowania zestawu. Chłodny jest fakt, że sprawdzenie, czy dana cyfra ma duplikaty, to O (1). Wiem, że ten wątek prawdopodobnie nie żyje, ale może to pomoże komuś! :)

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

Jest to rozszerzenie odpowiedzi @Puppy, która jest obecnie najlepszą odpowiedzią.

PS: Próbowałem wstawić ten wpis jako komentarz w obecnej najlepszej odpowiedzi przez @Puppy, ale nie mogłem, ponieważ nie mam jeszcze 50 punktów. Udostępniamy tu również trochę danych eksperymentalnych, aby uzyskać dalszą pomoc.

Zarówno std :: set, jak i std :: map są zaimplementowane w STL tylko przy użyciu drzewa wyszukiwania zbalansowanego. Tak więc oba prowadzą do złożoności O (nlogn) tylko w tym przypadku. Podczas gdy lepszą wydajność można osiągnąć, jeśli używana jest tablica asocjacyjna. std :: unordered_map oferuje implementację opartą na tablicy mieszania dla szybszego wyszukiwania. Eksperymentowałem ze wszystkimi trzema implementacjami i stwierdziłem, że wyniki używające std :: unordered_map są lepsze niż std :: set i std :: map. Wyniki i kod są udostępniane poniżej. Obrazy są migawką wydajności mierzonej przy pomocy rozwiązań LeetCode.

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 Wydajność (czas reakcji 52 ms tutaj)

Set/Mapa Wydajność

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