Java - Найти разницу между двумя массивами с дубликатами

Question

Я реализовал метод для нахождения разницы между двумя несортированными массивами. В настоящее время я добился получения различий без дубликатов. Но как заставить это учитывать дубликаты?
Например, для приведенных ниже входных массивов я ожидаю вывод [4 5 3]:

int[] arr1 = {1, 2, 3, 4, 5, 5};
int[] arr2 = {1, 2, 3, 5, 3};

Для этих входных массивов я ожидаю [7 7 9]

int[] arr3 = {7, 7, 4, 9, 6};
int[] arr4 = {4, 6};

//

static ArrayList<Integer> findDifference(int[] a, int[] b) {
    ArrayList<Integer> arr1 = new ArrayList<Integer>() {
        { for (int i : a) add(i); }
    };
    ArrayList<Integer> arr2 = new ArrayList<Integer>() {
        { for (int i : b) add(i); }
    };

    if (arr1.size() > arr2.size()) {
        arr1.removeAll(arr2);
        return arr1;
    } else {
        arr2.removeAll(arr1);
        return arr2;
    }
}

Answer 1

Вы можете сохранить count для каждого значения в первом массиве. Вы можете использовать HashMap для хранения количества вхождений для указанного значения c.

Затем для каждого value во втором массиве вы можете уменьшить уже рассчитанное число для этого value. В конце концов, если значение для указанного c значения равно 0, это будет означать, что в обоих массивах было одинаковое количество появлений. В противном случае один из массивов содержал больше экземпляров value. Число разностей для указанного c value будет abs(count[value]) (поскольку оно может стать отрицательным в случае, когда второй массив содержит больше экземпляров value, чем первый массив).

Этот Java код иллюстрирует подход:

public List<Integer> findDiff(int[] first, int[] second) {
  Map<Integer, Integer> count = new HashMap<>();
  for (int value : first) {
    int current = count.getOrDefault(value, 0);
    count.put(value, current + 1);
  }
  for (int value : second) {
    int current = count.getOrDefault(value, 0);
    count.put(value, current - 1);
  }
  List<Integer> result = new ArrayList<>();
  for (Map.Entry<Integer, Integer> entry : count.getEntrySet()) {
    int diff = entry.getValue();
    int times = Math.abs(diff);
    for (int i = 0; i < times; i++) {
      result.add(entry.getKey());
    }
  }
  return result;
}

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

Answer 2

Почти наверняка не оптимальное решение, но, как можно надеяться, вы можете работать с ним:

private static <X> Collection<X> findDiff(final Collection<X> a, final Collection<X> b) {
    // Copy the Collections so you don't modify inputs
    // and so you can safely 'remove' from them.
    final List<X> aCopy = new ArrayList<>(a);
    final List<X> bCopy = new ArrayList<>(b);

    // Remove all common elements from the copies
    // Using 'removeAll' will pull out duplicates,
    // so do this one-by-one.
    for (final X bElement : b) {
        aCopy.remove(bElement);
    }
    // Note it's important to iterate over 'a' here, not
    // aCopy since the elements of aCopy (may) have had some
    // entries 'remove'd.
    for (final X aElement : a) {
        bCopy.remove(aElement);
    }

    // Combine the two cleared out lists to find
    // the cumulative difference.
    final List<X> diff = new ArrayList<>(aCopy);
    diff.addAll(bCopy);

    return Collections.unmodifiableCollection(diff);
}

Обратите внимание, что вы можете конвертировать int[] в Collection<Integer>, используя что-то простое, например:

IntStream.of(arr).boxed().collect(Collectors.toList());

Обратите внимание: вы можете сделать это с меньшим количеством промежуточных Collection с. Вам нужно только скопировать один из входных, если вы не возражаете против изменения входных данных. И вам не нужно объединять эти два в новый diff. Это было просто чем-то, с чем можно было работать (и более объяснительным).

Answer 3

Вот решение, которое работает с обоими примерами:

public static void main(String[] args) {
    int[] arr1 = {1, 2, 3, 4, 5, 5};
    int[] arr2 = {1, 2, 3, 5, 3};
    System.out.println(findDifference(arr1, arr2));
    int[] arr3 = {7, 7, 4, 9, 6};
    int[] arr4 = {4, 6};
    System.out.println(findDifference(arr3, arr4));
}
static ArrayList<Integer> findDifference(int[] a, int[] b) {
    ArrayList<Integer> list1 = new ArrayList<Integer>();
    Arrays.stream(a).forEach(e -> list1.add(e));
    ArrayList<Integer> list2 = new ArrayList<Integer>();
    Arrays.stream(b).forEach(e -> list2.add(e));

    ArrayList<Integer> list1Copy = new ArrayList<Integer>();
    ArrayList<Integer> list2Copy = new ArrayList<Integer>();
    list1Copy.addAll(list1);
    list2Copy.addAll(list2);

    list1.forEach(e -> list2Copy.remove(e));
    list2.forEach(e -> list1Copy.remove(e));
    list1Copy.addAll(list2Copy);
    return list1Copy;
}

вывод:

[4, 5, 3] [7, 7, 9]

Принцип состоит в том, что процесс удаления операции копирования должен быть возможность повторения в начальном списке

Answer 4

Если вам нужна абсолютная разница между двумя массивами (в данном случае единственным отличающимся элементом является 4), вы можете рассчитать объединение и пересечение двух множеств.

Чтобы исключить дубликаты, вы можете также используйте Set вместо List, чтобы гарантировать уникальность. Очень простой пример может быть следующим:

    public static void main(String... args) {
        Integer[] arr1 = {1, 2, 3, 4, 5, 5};
        Integer[] arr2 = {1, 2, 3, 5, 3};

        Set<Integer> diffs = findDiff(arr1, arr2);
        diffs.forEach(System.out::println);
    }

    public static Set<Integer> findDiff(Integer[] array1, Integer[] array2) {
        List<Integer> list1 = Arrays.asList(array1);
        List<Integer> list2 = Arrays.asList(array2);
        Set<Integer> union = new HashSet<>(list1);
        union.addAll(list2);
        Set<Integer> intersection = new HashSet<>(list1);
        intersection.retainAll(list2);
        union.removeAll(intersection);
        return union;
    }