Hello,

On m'a récemment poser une question intéressante (pour une fois ) lors d'un entretien d'embauche :
Comment trouver des paires dans une liste de nombres et quelle est la complexité ?
Exemple : Dans la liste [1, 1, 1, 2, 4, 2, 2, 2]
Résultats : 3 paires (1, 2, 2), il y a 3 '1' -> on peut faire qu'une seule paire avec et 4 '2' -> 2 paires de '2'

Il y a une solution en O(n), on ajoute tous les nombres dans une hash map, et pour chaque nombre on divise le nombre d’occurrences par deux.
code (C++)
Code C++ : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
std::unordered_map<int, int> hm;
auto nbs = {1, 1, 1, 2, 4, 2, 2, 2};
for(auto n: nbs) {
   ++hm[n];
}
int nbPairs = 0;
for(auto const& kv: hm) {
   nbPairs += (kv.second / 2);
}
std::cout << nbPairs << std::endl;

Puis, puis même question pour trouver des triplets.
Exemple : Dans la liste [1, 1, 1, 2, 4, 2, 2, 2]
Résultats : 2 triplets (1, 2), il y a 3 '1' -> 1 triplet; 4 '2' -> 1 triplet

Sur le coup, j'ai donné un algo en O(n²), qui en y réfléchissant n'a pas de sens : appliquer 2 fois l'algo précédent de manière imbriqué. La complexité en O(n²) que j'ai donné n'a pas choqué, l'algo par contre ... :p
Alors que le même algo en O(n) semble marcher :
Code C++ : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
std::unordered_map<int, int> hm;
auto nbs = {1, 1, 1, 2, 4, 2, 2, 2};
for(auto n: nbs) {
   ++hm[n];
}
int nbPairs = 0;
for(auto const& kv: hm) {
   nbPairs += (kv.second / 3);
}
std::cout << nbPairs << std::endl;

Du coup ma question : Si une complexité en O(n²) ne choque pas, c'est qu'il y a un algo (probablement naïf); Mais j'arrive pas à trouver, une idée ?