Лучший способ удалить дубликаты из многомерного массива?

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

Самый простой ответ: Сравните элементы массива попарно и удалите дубликаты. Это не будет хорошо масштабироваться, но может и не понадобиться.

Сложнее: посмотрите на что-то вроде radix sort . После того, как вы отсортировали по первым, а затем по вторым элементам подмассивов, вы можете просмотреть весь массив и удалить дубликаты. Это будет лучше масштабироваться, но это может быть слишком излишним (в зависимости от вашей ситуации).

Наилучший (вероятно): создать набор элементов массива. Пройти через массив; для каждого элемента проверьте, есть ли он уже в наборе. Если это так, удалите его из массива. Если нет, добавьте его в набор и продолжайте. Это, вероятно, лучший подход, если дублирование массива не является проблемой с пространством.

Answer 2

Вам не нужно составлять набор всех точек - только значений Y для каждого X, потому что они отсортированы по X. Использование HashSet требует автобоксования каждого значения - в вопросах эффективности используйте TDoubleHashSet вместо.Это, вероятно, где-то близко к оптимальному - частично зависит от частоты дубликатов.

Это так же упорядочено, как и вход, но когда есть несколько значений Y для данного значения X, они могут выводиться в другом порядке.чем на входе.

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

Каков наилучший способ удаления дубликатов в массиве в Java?

Помогает ли это вообще?

Answer 4

создать набор элементов 'массива'. Элемент 'массива' должен возвращать равный true, если он содержит одинаковые элементы.

Answer 5

Одна простая вещь, которую вы можете сделать, это проверить, прежде чем добавлять новый элемент в ваш массив.