c# - 使用映射从点集合中删除重复项

Question

我有一个点数组，我们称它为 rawPoints，其中包含重复项。事实上，几乎每个点都重复了 2 到 6 次。在某处 重复，而不是在连续的位置。我想删除重复项以获得一个新集合，我将其称为 goodPoints。另外，我想知道从 rawPoints 到 goodPoints 的映射。换句话说，对于 rawPoints 中的每个点 P，我想知道(唯一)索引 i 使得 goodPoints[i] = P。

我正在用 C# 编写代码，所以我想知道是否有任何 .NET 集合对此有所帮助。

我读到过使用 HashSet 是删除重复项的好方法。但这不会给我映射。

一个可能的解决方案是“AddorFind(P)”函数，我可以使用它来将点 P 添加到 goodPoints。如果 P 还不是 goodPoints 的成员，则 AddorFind(P) 将添加它。如果 P 已经是 goodPoints 的成员，则 AddorFind(P) 将返回一个索引 i，使得 goodPoints[i] = P。

是否存在类似的东西，或者是否有其他一些简单且相当快速的解决方案？

Answer 1

尽管HashSet<Point>将无助于在 goodPoints 中找到唯一索引, 一个 Dictionary<Point,int>会的。

除了一个List<Point> goodPoints , 编字典 Dictionary<Point,int> mappings映射指向 goodPoints 中的索引列表。当你通过 rawPoints数组，遵循这个算法:

• 检查是否rawPoints[i]在mappings .如果是，继续下一点
• 否则，添加当前长度goodPoints至 mappings对于 rawPoints[i] , 然后添加 rawPoints[i]到 gooodPoints列表。

假设您的 Point表示有一个很好的散列函数，而且它覆盖了 Equals正确地，这个算法产生了一个列表 goodPoints和 O(N) 中的映射。