¿Una manera más elegante de buscar duplicados en una matriz C++?

Question

escribí este código en C++ como parte de una tarea uni donde necesito para asegurarse de que no hay duplicados dentro de una matriz:

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

Funciona perfectamente, pero me gustaría saber si hay una forma más elegante o eficiente de verificar.

Answer 1

Puede ordenar la matriz en O (nlog (n)), luego simplemente mire hasta el siguiente número. Eso es sustancialmente más rápido que su algoritmo existente O (n^2). El código también es mucho más limpio. Su código tampoco garantiza que no se insertaron duplicados cuando se volvieron a ingresar. Primero debe evitar que los duplicados existan.

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

También solicité la segunda recomendación para utilizar un conjunto estándar: no hay duplicados allí.

Answer 2

Puede agregar todos los elementos de un conjunto y verificar al agregar si ya está presente o no. Eso sería más elegante y eficiente.

Answer 3

Está bien, especialmente para longitudes de pequeñas series. Utilizaría enfoques más eficientes (menos de n^2/2 comparaciones) si la matriz es mucho mayor: consulte la respuesta de DeadMG.

Algunas pequeñas correcciones sobre su código:

• En lugar de int j = i escritura int j = i +1 y se puede omitir la prueba if(j != i)
• Usted DEBERÍAMOS necesita declarar i variable fuera la declaración for.

Answer 4

De hecho, el más rápido y por lo que puedo ver más elegante método es tal como se aconseja arriba:

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

Es O (n log n). Sin embargo, esto no significa que sea, si el orden de los números en la matriz de entrada necesita ser mantenido ... En este caso lo hice:

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

que todavía es O (n log n) y mantiene el original ordenamiento de elementos en tUserNumbers.

Cheers,

Paul

Answer 5

La siguiente solución se basa en la clasificación de los números y luego eliminar los duplicados:

#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

No estoy seguro de por qué esto no tiene se sugirió, pero aquí hay una manera en la base 10 para encontrar duplicados en O (n) .. El problema que veo con la solución O (n) ya sugerida es que requiere que los dígitos se ordenen primero ... Este método es O (norte) y no requiere que el conjunto sea ordenado. Lo bueno es que comprobar si un dígito específico tiene duplicados es O (1). Sé que este hilo probablemente esté muerto, pero ¡quizás ayude a alguien! :)

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

Es una extensión de la respuesta de @Puppy, que es la mejor respuesta actual.

PD: Intenté insertar esta publicación como comentario en la mejor respuesta actual por @Puppy pero no pude, ya que aún no tengo 50 puntos. También se comparten algunos datos experimentales aquí para obtener más ayuda.

std :: set y std :: map se implementan en STL utilizando solo el árbol de búsqueda binaria equilibrada. Entonces ambos conducirán a una complejidad de O (nlogn) solo en este caso. Mientras que el mejor rendimiento se puede lograr si se utiliza una tabla hash. std :: unordered_map ofrece implementación basada en tablas hash para una búsqueda más rápida. Experimenté con las tres implementaciones y encontré los resultados usando std :: unordered_map para ser mejor que std :: set y std :: map. Los resultados y el código se comparten a continuación. Las imágenes son la instantánea del rendimiento medida por LeetCode en las soluciones.

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 rendimiento (tiempo de ejecución fue de 52 ms aquí)

Set/Mapa Rendimiento

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