2016-10-03 9 views
0

2つのカテゴリA &のいずれかに属する要素のリストがあります。各要素はプロパティPを持っています。異なるカテゴリに属する​​任意の2つの要素。同じプロパティ値を共有し、このルールに違反する要素のすべてのセットを見つける必要があります。 C++ STL/boostライブラリを使用して実装する最も簡単な方法は何ですか?私はgcc 4.8.3を使用しています。したがって、C++ 14以降を必要とするソリューションは動作しません。STLを使用して反対のcatgeories間で一致するプロパティを持つ要素を見つけるアルゴリズム

+0

入力データの小さな例を提供してください。あなたのテストデータを引き受けることは困難です。 – Naidu

+0

idkあなたのケースについて....しかし、私が似たような状況にあるときは、代わりに['std :: unordered_set'](http://en.cppreference.com/w/cpp/container/unordered_set)を好むそのような問題は決して起こらないようにしなければならない。 –

答えて

1

Pのリストをソートすると、同じPを持つすべての要素が一緒になります。だから今リストを歩くことができ、それぞれの隣接するペアについて、それらが同じPを持ち、異なるカテゴリーのものであるかどうかをチェックすることができます。

ソートの場合はO(n log n)、リストをウォークしてチェックする場合はO(n)です。

関連する問題