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

本文关键字：删除 集合 映射 点集 | 更新日期: 2023-09-27 18:25:34

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

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

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

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

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

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

虽然HashSet<Point>不会帮助在goodPoints中找到唯一的索引，但Dictionary<Point,int>会。

除了 List<Point> goodPoints 之外，创建一个字典Dictionary<Point,int> mappings，将指向列表中的索引映射到goodPoints索引。当您遍历rawPoints数组时，请遵循以下算法：

  • 检查rawPoints[i]是否在mappings。如果是，请继续到下一点
  • 否则，将当前长度的goodPoints添加到rawPoints[i]的mappings，然后将rawPoints[i]添加到gooodPoints列表中。

假设您的Point表示形式具有良好的哈希函数，并且它正确地覆盖了Equals，则此算法会生成goodPoints列表和 O(N( 中的映射。

您将需要两个输出：

  1. "好点"列表。
    2. 将索引数组映射到良好点数组中，
  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;
        }
    }
}

您可以使用 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));
}

您可以创建一个 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();
相关文章：