Подтвердить что ты не робот

Поддерживать ArrayList уникальных массивов в Java

Как мне сохранить ArrayList уникальных массивов?

Например, если у меня есть следующие массивы:

int [] a = {1,2,3};
int [] b = {2,1,3};
int [] c = {2,1,3};

В соответствии с моей логикой я рассматриваю уникальные комбинации. Таким образом, в случае выше a = b = c, потому что все они содержат "1", "2", "3".

В идеале мне интересно, есть ли в Java структура данных, которая распознает это.

Я попробовал следующее:

Set<int []> result = new LinkedHashSet<>();
int [] x = {1,2,3};
int [] z = {2,1,3};
int [] m = {2,1,3};

result.add(x);
result.add(z);
result.add(m);

for(int [] arr: result){
    printArray(arr);
}

Мой вывод был:

1 2 3
2 1 3
2 1 3

В идеале я хотел бы, чтобы мой вывод печатал только одну из указанных выше комбинаций.

4b9b3361

ОТВЕТЫ

Ответ 1

Вы можете создать метод для добавления, если он не равен следующим образом:

public static Set<int[]> addIfNotExist(Set<int[]> result, int[] array) {
    boolean check = result.stream()
            .anyMatch(a -> {
                Arrays.sort(a);
                Arrays.sort(array);
                return Arrays.equals(a, array);
            });
    if (check) {
        return result;
    } else {
        result.add(array);
        return result;
    }
}

Затем вы можете вызвать свой метод так:

result = addIfNotExist(result, x);
result = addIfNotExist(result, z);
result = addIfNotExist(result, m);

Выход

[1, 2, 3]

Или, если вы используете статический Set, вы можете просто использовать:

static Set<int[]> result = new LinkedHashSet<>();

public static void main(String[] args) {

    int[] x = {1, 2, 3};
    int[] z = {2, 1, 3};
    int[] m = {2, 1, 3};

    addIfNotExist(result, x);
    addIfNotExist(result, z);
    addIfNotExist(result, m);

    for (int[] arr : result) {
        System.out.println(Arrays.toString(arr));
    }
}

public static void addIfNotExist(Set<int[]> result, int[] array) {
    boolean check = result.stream()
            .anyMatch(a -> {
                Arrays.sort(a);
                Arrays.sort(array);
                return Arrays.equals(a, array);
            });
    if (!check) {
        result.add(array);
    }
}

Ответ 2

Это определенно кажется хакерским и неправильным, но вы можете использовать TreeSet с пользовательским Comparator. В зависимости от ваших потребностей это может сработать, но, по крайней мере, обратите внимание, что это нарушает общий контракт интерфейса Set.

class Demo {
    public static void main(String[] args) throws Exception {
        Set<int[]> result = new TreeSet<>(new Hack());
        int[] x = {1,2,3};
        int[] z = {2,1,3};
        int[] m = {2,1,3};

        result.add(x);
        result.add(z);
        result.add(m);

        for (int[] arr : result) {
            System.out.println(Arrays.toString(arr));
        }
    }
}

class Hack implements Comparator<int[]> {

    @Override
    public int compare(int[] e1, int[] e2) {
        int[] copy1 = Arrays.copyOf(e1, e1.length);
        int[] copy2 = Arrays.copyOf(e2, e2.length);
        Arrays.sort(copy1);
        Arrays.sort(copy2);
        return Arrays.compare(copy1, copy2);
    }
}

Выход:

[1, 2, 3]

Если вы все еще на Java 8, используйте эту реализацию Hack:

class Hack implements Comparator<int[]> {

    @Override
    public int compare(int[] e1, int[] e2) {
        int[] copy1 = Arrays.copyOf(e1, e1.length);
        int[] copy2 = Arrays.copyOf(e2, e2.length);
        Arrays.sort(copy1);
        Arrays.sort(copy2);
        int cmp = Integer.compare(copy1.length, copy2.length);
        if (cmp != 0) {
            return cmp;
        }
        for (int i = 0; i < copy1.length; i++) {
            cmp = Integer.compare(copy1[i], copy2[i]);
            if (cmp != 0) {
                return cmp;
            }
        }
        return 0;
    }
}

Ответ 3

Если мы предполагаем, что ваши массивы не могут содержать несколько раз одно и то же целое число (например, [1, 1, 2]), тогда ваше определение уникальности (имеющее одинаковые элементы независимо от порядка) для вашего массива - это набор, поэтому вы можете использовать набор из набора.

public static void main(String[] args){
    Set<Set<Integer>> result = new HashSet<>();
    int [] x = {1,2,3};
    int [] z = {2,1,3};
    int [] m = {2,1,3};

    result.add(arrayToSet(x));
    result.add(arrayToSet(z));
    result.add(arrayToSet(m));

    System.out.println(result);

}

private static Set<Integer> arrayToSet(int [] arr){
    return Arrays.stream(arr).boxed().collect(Collectors.toSet());
}

Если вы хотите сохранить свои массивы, то какой из них следует хранить, если два массива имеют одинаковые элементы? Если это первый добавленный объект, вы можете использовать Map<Set<Integer>, int[]>, а затем значения вашей карты содержат массивы.

Если вам нужно учесть, что может содержать несколько раз одно и то же целое число, то это мультисеты. Вы можете реализовать Multiset с помощью Map<Integer, Integer>, который подсчитывает, сколько раз присутствует каждый элемент. Тогда вы можете использовать ту же реализацию, но с Set<Map<Integer, Integer>> вместо Set<Integer>:

public static void main(String[] args){
    Set<Map<Integer,Long>> result = new HashSet<>();
    int [] x = {1,2,3};
    int [] z = {1,2,2,3};
    int [] m = {1,2,3,2};

    result.add(arrayToMultiSet(x));
    result.add(arrayToMultiSet(z));
    result.add(arrayToMultiSet(m));

    System.out.println(result);

}

private static Map<Integer,Long> arrayToMultiSet(int [] arr){
    return Arrays.stream(arr).boxed().collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
}

Примечание. Я использовал Map<Integer,Long>, потому что Collectors.counting() возвращает коллектор Long.

Ответ 4

Вы можете создать класс-оболочку, который будет содержать неизменяемую переменную экземпляра целочисленного массива и переопределить хеш-код:

public class ArrayWrapper {
   private final int[] a;

@Override
public int hashCode(){
 //your implementation 
}
@Override
 public boolean equals(){
  // your implementation 
 }
}

И тогда вы можете использовать:

Set<ArrayWrapper> set = new HashSet<>();

Ответ 5

То, что вам нужно, это набор целых чисел, и если для вас важен относительный порядок, вы можете использовать что-то вроде этого:

import java.util.Set;
import java.util.LinkedHashSet;
import java.util.Arrays;
import java.util.stream.Collectors;

public class HelloWorld
{
  public static void main(String[] args)
  {
        Set<Set<Integer>> result = new LinkedHashSet<>();
        int[] x = {1, 2, 3};
        int[] z = {2, 1, 3};
        int[] m = {2, 1, 3};

        result.add(Arrays.stream(x).boxed().collect(Collectors.toCollection(LinkedHashSet::new)));
        result.add(Arrays.stream(z).boxed().collect(Collectors.toCollection(LinkedHashSet::new)));
        result.add(Arrays.stream(m).boxed().collect(Collectors.toCollection(LinkedHashSet::new)));

        System.out.println(result);
  }
}

Вы также можете извлечь Arrays.stream(x).boxed().collect(Collectors.toCollection(LinkedHashSet::new)) в отдельную функцию.

Ответ 6

@Test
    public void testArraysSet() {
        Set<int[]> myArrays = new TreeSet<>((arr1, arr2) -> {
            Arrays.sort(arr1);
            Arrays.sort(arr2);
            return Arrays.equals(arr1, arr2) ? 0 : 1;
        });

        int [] a = {1,2,3};
        int [] b = {2,1,3};
        int [] c = {2,1,3};

        myArrays.add(a);
        myArrays.add(b);
        myArrays.add(c);

        assertEquals(1, myArrays.size());
    }

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

Ответ 7

Уже были некоторые ответы, но некоторые из них делают определенные предположения, которые не могут быть выведены из вопроса, другие предлагают определенные изменения, которые могут рассматриваться как обходные пути, а другие имеют определенные недостатки, которые не следует игнорировать.

Обращаясь к некоторым из них здесь:

  • Изменение элементов на Set<Integer> предполагает, что каждый элемент может появиться только один раз. Кроме того, если существующий код уже создает массивы int[], а нисходящий код нуждается в массивах int[], то использование полученной структуры данных будет неуклюжим:

    int array[] = somewhere.getArray();
Set<Integer> set = convert(array); // Convert array to set
data.add(set);
...
set = data.iterator().next();
array = convert(set);              // Convert set to array
somewhere.setArray(array);

    В зависимости от размера массивов это может повлиять на производительность и привести к перегрузке памяти.

  • Использование TreeSet<int[]> выглядит как простое и разумное решение. Самое приятное, что он может напрямую хранить массивы int[]. Но у него есть некоторые недостатки:

    1. Это подразумевает порядок. Больше нельзя использовать другую реализацию Set (например, LinkedHashSet), которая сохраняет порядок вставки
    2. Может быть немного сложно реализовать сравнение способом, который согласуется с equals, и в противном случае набор больше не будет подчиняться общему контракту интерфейса Set
    3. Простая, но правильная реализация сравнения, вероятно, будет включать сортировку массивов. Это означает, что массивы, возможно, придется либо модифицировать путем их вставки в набор, что, безусловно, является неприемлемым, либо создавать защитные копии массивов. Здесь следует помнить, что копирование и сортировка должны выполняться каждый раз, когда добавляется новый массив, и это должно быть выполнено несколько раз при переходе вниз по дереву., Хотя количество сравнений будет только O (log (n)) для набора с элементами n, сортировка будет принимать O (m log (m)) каждый раз для массивов длины m, что может быть чрезмерно дорогим.
  • Аналогичные аргументы могут быть применены для подходов, которые проверяют, существует ли уже "эквивалентный" массив перед вставкой нового. Кроме того, эти подходы не основаны на структуре данных, но должны быть частью кода, который использует структуру данных.

По этим причинам я бы выбрал подход, который в основном совпадает с подходом, который Михаил Москура упомянул в своем ответе: он основан на классе, который просто упаковывает данные массивы int[], и реализует equals и hashCode соответственно.

(Обратите внимание, что вы также можете позволить этому классу реализовать Comparable, добавив некоторую гибкость в отношении того, можно ли его поместить в TreeSet, если вы знаете о возможных трудностях и недостатках, упомянутых выше...)

В приведенном ниже примере этот класс называется UnorderedIntArray. Концептуально было бы предпочтительнее иметь Set<int[]>, а решение ниже должно использовать Set<UnorderedIntArray>. Но так как этот класс только переносит существующий массив, performance- и накладные расходы памяти практически равны нулю, и поэтому я по-прежнему считаю его выгодным по сравнению с преобразованием между int[] и некоторыми другими типами данных. Также обратите внимание, что метод equals в приведенном ниже примере не очень эффективен, но это простой способ обеспечить выполнение контрактов equals.

import java.util.Arrays;
import java.util.LinkedHashSet;
import java.util.Map;
import java.util.Set;
import java.util.function.Function;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class UniqueArraysTest {

    public static void main(String[] args) {
        Set<UnorderedIntArray> result = new LinkedHashSet<>();
        int[] x = { 1, 2, 3 };
        int[] y = { 2, 1, 3 };
        int[] z = { 2, 1, 3 };

        int[] u = { 1, 1, 1, 2, 3 };
        int[] v = { 1, 1, 1, 2, 3 };
        int[] w = { 1, 1, 1, 1, 3 };

        result.add(new UnorderedIntArray(x));
        result.add(new UnorderedIntArray(y));
        result.add(new UnorderedIntArray(z));
        result.add(new UnorderedIntArray(u));
        result.add(new UnorderedIntArray(v));
        result.add(new UnorderedIntArray(w));

        for (UnorderedIntArray a : result) {
            int[] array = a.getArray();
            System.out.println(Arrays.toString(array));
        }

    }

    static class UnorderedIntArray {
        private final int array[];

        UnorderedIntArray(int array[]) {
            this.array = array;
        }

        int[] getArray() {
            return array;
        }

        @Override
        public int hashCode() {
            return IntStream.of(array).sum();
        }

        @Override
        public boolean equals(Object object) {
            if (object == this) {
                return true;
            }
            if (object == null) {
                return false;
            }
            if (!(object instanceof UnorderedIntArray)) {
                return false;
            }
            UnorderedIntArray that = (UnorderedIntArray)object;
            if (this.array.length != that.array.length) {
                return false;
            }
            // This is very simple, but not very efficient. More efficient
            // solutions could be implemented, but they are not trivial...
            Map<Integer, Long> thisFrequencies = computeFrequencies(this.array);
            Map<Integer, Long> thatFrequencies = computeFrequencies(that.array);
            return thisFrequencies.equals(thatFrequencies);
        }

        private Map<Integer, Long> computeFrequencies(int array[]) {
            return Arrays.stream(array).boxed().collect(
                Collectors.groupingBy(Function.identity(), Collectors.counting()));
        }

        @Override
        public String toString() {
            return Arrays.toString(array);
        }

    }
}

Для ввода

int[] x = { 1, 2, 3 };
int[] y = { 2, 1, 3 };
int[] z = { 2, 1, 3 };
int[] u = { 1, 1, 1, 2, 3 };
int[] v = { 1, 1, 1, 2, 3 };
int[] w = { 1, 1, 1, 1, 3 };

результат - ожидаемый

[1, 2, 3]
[1, 1, 1, 2, 3]
[1, 1, 1, 1, 3]