c++ - map<int,vector<int>> 的算法

Question

我在想出一个有效的算法来解决我遇到的 map vector 问题时遇到了麻烦。

假设我有一个 map> 我想知道一个整数在 map 的所有 vector 中出现了多少次，如果它出现在预定义的数量上，则从中删除它的值其余的 vector (希望这是有意义的)，这是一个简单的例子:

---

关键值

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

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

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

在这种情况下，如果它出现超过三次，我想从所有 vector 中删除 4。生成的 map 如下所示:

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

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

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

---

我正在为这个问题寻找一种有效的算法，只是想知道是否有人有任何想法。 (我在 C++ 工作，但我知道 java 或伪代码很酷)。

感谢您的帮助

旁注，仅在此示例中， vector 在现实生活中并未排序。

Answer 1

由于 vector 未排序，因此执行此操作的唯一方法是遍历所有 vector 的所有项，跟踪已找到的项，并根据需要清理 vector 。我认为使用外部有状态谓词和删除-删除习语来执行此操作会很简单。

但是，鉴于您的确切需求和容器使用情况，可能会有其他方法可用。例如，如果 vector 实际上不需要可索引，您可以使用 multiset 来保持项目排序并提供简单的计数和删除。