从多维数组中删除重复项的最佳方法

Question

假设我有一个数组:

double[][] points = {{0.0, 0.0}, {1.0, 1.0}, {1.0, 1.0},  {2.0, 2.0}};

我想创建一个没有重复条目{1.0, 1.0}的新数组-这样做的最佳方法是什么?

附加信息:

• 数组是排序的，但只按第一个组件排序，所以可以有

  {1.0, 2.0}, {1.0, 1.0}, {1.0, 2.0}
  

  这就是我获取数据的方式，我不能改变初始排序机制

• 两个维度是目前的限制，但数组可以有数千个点

Answer 1

最简单的回答:按对比较数组中的元素并删除重复的元素。这将不能很好地扩展，但它可能不需要。

更复杂:看看基数排序之类的东西。在按子数组的第一个元素和第二个元素排序之后，您可以遍历整个数组并删除重复项。这将更好地扩展，但它可能很容易被过度使用(取决于您的情况)。

Best (probably):创建一组数组元素。遍历数组;对于每个元素，检查它是否已经在集合中。如果是，将其从数组中移除。如果没有，把它添加到集合中，然后继续。这可能是最好的方法，除非重复数组是一个空间问题。

Answer 2

您不需要创建所有点的集合—只需要每个X的Y值，因为它们是在X上排序的。使用HashSet需要自动装箱每个值—考虑到效率问题，请使用TDoubleHashSet代替。这可能是接近最佳的——部分取决于重复的频率。

这与输入一样有序，但是当给定的X值有多个Y值时，它们可能以与输入不同的顺序输出。

double prevPoint[];
// If efficiency matters, use Trove TDoubleHashSet instead.
HashSet<Double> set;
ArrayList<double[]> buffer;
double[][] filter(double[][] points)
{
    prevPoint = new double[]{Double.NaN, Double.NaN};
    set = new HashSet<Double>();
    // Allocate space as if there were no duplicates.
    // Tweak if expecting lots of dupes.
    buffer = new ArrayList<double[]>(points.length);
    for ( double[] point : points )
    {
        if ( prevPoint[0] != point[0] )
        {
            emitSet();
            set.clear();
        }
        set.add(point[1]);
        prevPoint = point;
    }
    // output hashset
    emitSet();
    return buffer.toArray(new double[buffer.size()][2]);
}
private void emitSet()
{
    for ( double y : set )
    {
        // optimize out array create for common case of only 1 y with the same x.
        // get rid of this complexity if efficiency not needed.
        if ( y == prevPoint[1] )
        {
            buffer.add(prevPoint);
        }
        else
        {
            buffer.add(new double[] {prevPoint[0], y});
        }
    }
}

Answer 3

创建数组元素集。

Answer 4

在Java中删除重复项的最佳方法是什么?

这有帮助吗?

Answer 5

您可以做的一件简单的事情是在向数组中添加新元素之前进行检查。