Comment trouver le meilleur correspondant pour toutes les colonnes d'un tableau 2D?

Question

Disons que j'ai un tableau 2D qui ressemble à:

________________ 
|10|15|14|20|30| 
|14|10|73|71|55| 
|73|30|42|84|74| 
|14|74|XX|15|10| 
---------------- 

Comme je l'ai montré, les colonnes ne doivent pas nécessairement être la même taille.

Maintenant, j'ai besoin de trouver la meilleure correspondance pour chaque colonne (celle qui a le plus exactement les mêmes éléments et les plus différents). Bien sûr, je pourrais le faire en n^2 mais c'est trop lent pour moi. Comment puis-je le faire?

J'ai pensé à un arbre de dimension k et de trouver le voisin le plus proche pour chacun d'eux, mais je ne sais pas si c'est bon et ça marchera comme je veux (probablement pas).

Résultat par exemple:

• La première colonne est le plus susceptible troisième (seulement trois différents - 10, 14, 42)
• Deuxième colonne -> cinquième (seulement deux différents - 15 et 55)

et ainsi de suite et ainsi de suite ... :)

Answer 1

Si vous savez que tous les chiffres du tableau sont des nombres à 2 chiffres (soit 10 = < x < 100), pour chaque colonne, créez un tableau de booléens où vous marquerez les nombres existants:

bool array[5][100]; 
std::fill(&array[0][0], &array[0][0] + sizeof(array) , false); // init to false 
for (int i = 0; i < 5; i++) 
{ 
    for (int j = 0; j <5; j++) 
    { 
    array[i][table[i][j]] = true; 
    } 
} 

Devrait être facile à partir de là.