Bienvenue à tous!
Je suis Oleg. Spécialisation: noyaux C ++ / C / OS / pilotes / matériel / réseaux / embarqués. Je vis et travaille à l'étranger depuis environ un an et demi. Maintenant en Finlande, avant cela, il y avait la Pologne. Ils m'ont parlé des particularités de déménager dans les deux pays avant moi, qui est intéressé - écrivez, je répondrai à vos questions. Beaucoup a également été écrit sur la vie dans ces pays. Mais un jour je présenterai mes impressions des deux sous la forme d'un essai gratuit.
Maintenant, je veux parler d'un problème que j'ai passé une demi-journée à résoudre, même si cela n'en valait pas la peine. Et le plus drôle, c'est que j'ai résolu des problèmes similaires dans les interviews. Je l'ai rencontrée en creusant l'un de mes projets de maison.
Donc, étant donné un certain nombre d'ensembles d'entiers de tailles différentes. Vous devez trouver les nombres qui sont dans tous les ensembles sauf un. L'index de l'ensemble où l'élément est manquant est également requis.
Supposons qu'il existe des ensembles {1, 2, 3}, {3, 0, 4}, {5}. Dans cet exemple artificiel, l'élément {3}, qui est présent dans les ensembles zéro et premier et absent dans le second, prétend être une trouvaille. Il peut également être écrit comme un ensemble {3, 2}. Littéralement, cet enregistrement est déchiffré comme suit: la valeur 3 est absente de l'ensemble 2. Encore une condition: seuls les entiers positifs de 1 à 64 participent. Les éléments de chaque ensemble sont uniques.
Fondamentalement, il s'agit d'une sorte de généralisation du problème classique des entretiens. Ce dernier est formulé comme suit: les nombres sont reçus à l'entrée d'un certain bloc du programme, il faut couper les doublons. Il peut être résolu de manière élémentaire en utilisant la primitive STL unordered_set. C'est bien car il a O (1) - temps de recherche constant pour de courtes séquences de nombres. Dans le cadre d'une tâche limitée, il est assez agréable à lui-même en goût et en couleur. De plus, lors de l'ajout d'un doublon, il ne l'ajoutera tout simplement pas. Il n'est pas non plus nécessaire de vérifier la valeur de retour dans ce cas. Autrement dit, nous avons une économie de trois lignes de code, qui sont de toute façon contenues dans l'implémentation du modèle. Mais, comme mon projet a une gamme limitée de nombres, vous pouvez vous en passer. Oui, si vous étendez la plage de nombres, alors unordered_set, ou quelque chose comme ça, vous devez utiliser.
Pour plus de simplicité, définissons le nombre d'ensembles égal à 3. L'ensemble est stocké dans un vecteur, ou vecteur modèle STL <vecteur>. Le résultat est un ensemble de paires de nombres non négatifs vector <pair <int, int >>. Dans une paire, en premier lieu est l'élément lui-même, dans le second est l'index de l'ensemble où il n'est pas.
void PrepareData(const vector<vector<int> >& src, vector<pair<int, int> >& res)
{
vector<pair<int, int> > data(MAX); //
for(unsigned i(0); i < src.size(); ++i)
{
const auto& rf(src[i]);
for(unsigned j(0); j < rf.size(); ++j)
{
ASSERT(((0 < rf[j]) && (MAX > rf[j])) && "!!! An invalid data !!!");
++data[rf[j]].first; //
data[rf[j]].second += i; //
}
}
auto fs(((src.size() - 1) * src.size()) >> 1); //
for(unsigned i(0); i < data.size(); ++i) //
{
if(data[i].first == src.size() - 1) //
{
pair<int, int> cur{i, 0}; //
cur.second = fs - data[i].second; // ,
res.push_back(cur);
}
}
}1)
2) . . , .
3) data . , , ,
4) , (a[1] + a[n]) * n / 2
5) , ,
6) , ,
C'est tout, une demi-journée de tourment. Le code ne prétend pas être beau. Le désir était seulement de présenter une idée ou une approche pour résoudre de tels problèmes. Remerciements particuliers à IlyaWataru, qui m'a recommandé de prêter attention à l'optimalité de mes algorithmes.
Lien vers le code https://yadi.sk/d/F2dLt6v_uvjKdQ