Поиск пар дубликатов в Java ArrayList

Question

Я ищу, чтобы найти количество дубликатов пар в Java ArrayList.

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

Пример использования набора данных [2,2,3,2,2]: 0: 1, 0: 3, 0: 4, 1: 3, 1: 4, 3: 4.Итак, ответ: шесть повторяющихся пар?

Answer 1

Вам просто нужно посчитать, сколько раз появляется каждое число (я бы пошел с картой здесь) и рассчитать 2-комбинации (http://en.wikipedia.org/wiki/Combination) этого числа для каждого числа со счетом> 1.

Так что в основном вам нужен метод для вычисления n!/k!(n-k)! с k, равным 2, и n, являющимся счетчиком.

Принимая ваш пример [2,2,3,2,2],число 2 появляется 4 раза, поэтому математика будет выглядеть так:

4! / 2! (4-2)!= 24/4 = 6 -> 6 пар

Если вы не хотите реализовывать функцию факториала, вы можете использовать ArithmeticUtils из Apache Commons, в них уже реализован факториал .

Answer 2

Если вы хотите избежать вложенных циклов (за счет наличия 2 циклов), вы можете:

1. для каждого числа в списке найдите, сколько раз повторяется каждое число (возможно, используйте карту с ключом = число, значение = раз, когда это число появилось в списке)
2. для каждого числа на карте, подсчитайте количество возможных комбинаций на основе времени, когда это произошло (0 или 1 раз = нет повторяющихся пар, 2 или более = n! / (2 * (n-2)!) = (n * (n-1)) / 2 повторяющихся пары)
3. сумма всех возможных комбинаций

Выполнение сортировки, подобной предложенной ElKamina, позволило бы оптимизировать этот метод.

Answer 3

Использование Гуава , если ваши элементы были String s:

Multiset<String> multiset = HashMultiset.create(list);
int pairs = 0;
for(Multiset.Entry<String> entry : multiset.entrySet()) {
  pairs += IntMath.binomial(entry.getCount(), 2);
}
return pairs;

Использует утилиты Multiset и math от Guava.

Answer 4

Сортируйте числа в первую очередь.Позже, если будет k копий данного числа, будет k*(k-1)/2 пар из этого числа.Теперь сложите все числа.