从点集合中删除重复项，带有映射

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。

类似这样的东西是否存在，或者是否有其他简单而又相对快速的解决方案？

- bubba

---

rawPoints 是否按照相同的点排列在一起，还是混合在一起？ - Matthew Watson

为什么需要唯一索引？看起来你只是想在非重复点上进行操作。 - Yuval Itzchakov

@MatthewWatson -- 搞混了 - bubba

@YuvalItzchakov -- 我有引用 rawPoints 成员的数据结构。我想将它们更改为引用 goodPoints 的索引。有意义吗？ - bubba

没关系，我明白你想做什么。你需要知道rawPoints的索引有特定的原因吗？ - Yuval Itzchakov

@YuvalItzchakov -- 我需要goodPoints的索引，因为这是我想要存储在我的数据结构中的内容。我正在将“三角形soup”转换为一个网格，其中每个三角形包含3个顶点索引。 - bubba

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方法，则此算法以O（N）时间复杂度生成goodPoints列表和映射。

- Sergey Kalinichenko

---

谢谢。这看起来比其他答案更有前途。也许有个打字错误吗？你写了“将rawPoints[i]添加到gooodPoints长度”。我怎么能将一个点添加到长度中呢？你是不是想说“将rawPoints[i]添加到gooodPoints数组中”？ - bubba

我有点担心“检查rawPoints [i]是否在映射中”。这不是O（N）操作吗？如果是，那么总过程就是O（N ^ 2），对吧？ - bubba

@bubba 不，因为mappings是一个基于哈希的容器Dictionary<Point,int>，所以查找的时间复杂度为O(1)。 - Sergey Kalinichenko

@bubba 是的，“length”应该改为“list”（已编辑）。我使用了一个列表而不是数组，这样我就可以添加项目而不必担心它们的数量。如果你需要一个数组，在最后调用ToArray将列表转换为数组即可。 - Sergey Kalinichenko

Answer 2

你需要两个输出：

1. "好点"列表。
2. 一个指向好点数组的索引数组，其长度与原始点数相同（因为你想将每个原始点索引映射到好点数组）。

我认为这段代码将生成这两个东西：

using System;
using System.Collections.Generic;
using System.Drawing;

namespace Demo
{
    class Program
    {
        static void Main()
        {
            var rawPoints = createRandomPoints(10000, 100, 100);

            int[] goodPointMap = new int[rawPoints.Length];
            var map = new Dictionary<Point, int>();
            var goodPoints = new List<Point>();

            for (int i = 0; i < rawPoints.Length; ++i)
            {
                Point p = rawPoints[i];
                int index;

                if (map.TryGetValue(p, out index))
                {
                    goodPointMap[i] = index;
                }
                else
                {
                    map[p] = goodPoints.Count;
                    goodPointMap[i] = goodPoints.Count;
                    goodPoints.Add(p);
                }
            }

            // At this point we no longer need 'map', which is used only to generate 'goodPoints[]'
            // and 'goodPointMap[]'.

            Console.WriteLine("Number of good points = " + goodPoints.Count);

            // Every point in rawPoints[] should have a point in goodPoints
            // which you can reference via goodPointMap[].
            // Let's verify that:

            for (int i = 0; i < rawPoints.Length; ++i)
                if (rawPoints[i] != goodPoints[goodPointMap[i]])
                    Console.WriteLine("Failed!");
        }

        static Point[] createRandomPoints(int n, int maxX, int maxY)
        {
            var rng    = new Random();
            var result = new Point[n];

            for (int i = 0; i < n; ++i)
                result[i] = new Point(rng.Next(maxX), rng.Next(maxY));

            return result;
        }
    }
}

- Matthew Watson

---

谢谢。看起来不错。这似乎是@dasblinkenlight建议的相同算法，是吗？即使是相同的算法，这段代码也非常有帮助。 - bubba

@bubba 这可能非常相似。我没有看他的答案，因为我正在忙着写这个。 :) 顺便说一下，行 if (map.TryGetValue(p, out index)) 是一个摊销 O(1) 操作，所以循环总体应该是 O(N)。 - Matthew Watson

仔细检查后，我的答案略有不同，因为我使用了一个单独的goodPointMap[]数组来将rawPoint[]索引映射到goodPoint[]索引。 - Matthew Watson

Answer 3

您可以使用 Linq 完成此操作：

List<Point> points = new List<Point>();
points.Add(new Point(1, 1));
points.Add(new Point(1, 1));
points.Add(new Point(1, 1));
points.Add(new Point(1, 2));
points.Add(new Point(1, 2));
points.Add(new Point(1, 2));

List<Point> goodPoints = new List<Point>();


foreach (Point p in points)
{
    goodPoints.Add(p);
    //goodPoints = goodPoints.Distinct().ToList();
    //int idx = goodPoints.IndexOf(p);
    int idx = (goodPoints = goodPoints.Distinct().ToList()).IndexOf(p);
    Debug.WriteLine(string.Format("Index of Point({0}, {1}) = {2}", p.X, p.Y, idx));
}

- gmiley

---

他不想计算唯一元素的数量。此外，Select(x => x) 是完全多余的。 - Yuval Itzchakov

计数仅用于显示唯一项目的数量，他仍将可以访问新的不同点列表。 - gmiley

我不确定这如何回答OP的要求，即保留旧列表中重复项的索引？ - Yuval Itzchakov

这个程序如何将rawPoints映射到goodPoints？换句话说，给定一个点P在rawPoints中，我如何找到索引i使得goodPoints[i] = P？ - bubba

修改后，只需将点添加到好的列表中，然后将列表重置为其自身的唯一，并返回 IndexOf(Point)。 - gmiley

Answer 4

你可以创建一个PointComparer类并在Distinct方法中使用它。

public class PointComparer : IEqualityComparer<Point>
{
    public bool Equals(Point p1, Point p2)
    {
        return p1.x==p2.x && p1.y == p2.y;
    }
    public int GetHashCode(Point p1)
    {
        return p1.x*p2.x;//bla bla
    }
}

而且

goodPoints = rawPoints.Distinct(new PointComparer()).ToList();

- agit

---

是的，我假设我需要编写自定义的“比较”或“相等”函数。给定一个在 rawPoints 中的点 P，您的代码如何告诉我 goodPoints 中对应的索引 i（即满足 goodPoints[i] = P 的索引 i）？ - bubba