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实际上不需要可索引，则可以使用 amultiset来保持项目排序并提供简单的计数和删除。

于 2012-10-09T15:12:08.937 回答