1

私が持っている地図ベクトルの問題に対して効率的なアルゴリズムを考え出すのに苦労しています。

map<int , vector <int> > があり、マップのすべてのベクトルで整数が何回発生するかを調べたいとします。それが定義済みの量を超えて発生した場合は、残りのベクトルからその値を削除します（うまくいけばそれは理にかなっています）、ここに簡単な例があります：

キー値

1 - <2,3,4,4,5>

2 - <2,3,3,4,5>

3- <2,3,3,4,6>

この場合、3 回以上発生した場合、すべてのベクトルから 4 を削除したいとします。結果のマップは次のようになります。

1 - <2,3,4,4,5>

2 - <2,3,3,4,5>

3- <2,3,3,DEL,6>

この問題の効率的なアルゴリズムを探していますが、誰かアイデアがあるかどうか疑問に思っていました. (私は C++ で作業していますが、Java または疑似コードが優れていることは知っています)。

助けてくれてありがとう

補足 この例では、ベクトルは実際にはソートされていないことに注意してください。

4

1 に答える 1

2

ベクトルは並べ替えられていないため、これを行う唯一の方法は、すべてのベクトルのすべての項目を反復処理し、見つかった数を追跡し、必要に応じてベクトルをクリーンアップすることです。これを外部ステートフル述語とremove-eraseイディオムで行うのは簡単だと思います。

ただし、正確なニーズとコンテナの使用を考えると、別のアプローチが利用できる場合があります。たとえば、vectorが実際にインデックス可能である必要がない場合は、multiset代わりにアイテムを並べ替えて保持し、簡単にカウントおよび削除できるようにすることができます。

于 2012-10-09T15:12:08.937 に答える