Задача: Посчитать количество пар чисел (number of equal pairs)
Исходник: Быстрый подсчет одинаковых пар чисел (number of equal pairs), язык: java [code #800, hits: 141]
автор: this [добавлен: 14.01.2022]
  1. import java.util.Arrays;
  2. import java.util.HashMap;
  3. import java.util.Map;
  4. import java.util.Optional;
  5. import java.util.function.IntFunction;
  6.  
  7. class EqualPairCounter {
  8.  
  9. int numberOfEqualPairsLinearithmic(int[] a) {
  10. Arrays.sort(a);
  11. int res = 0;
  12. int currPairs = 1;
  13. IntFunction<Integer> countFn = (cnt) -> cnt > 1 ? (cnt - 1) * cnt / 2 : 0;
  14. for (int i = 1; i < a.length; i++) {
  15. if (a[i] == a[i - 1]) {
  16. currPairs++;
  17. } else {
  18. res += countFn.apply(currPairs);
  19. currPairs = 1;
  20. }
  21. }
  22.  
  23. res += countFn.apply(currPairs);
  24. return res;
  25. }
  26.  
  27. public static void main(String[] args) {
  28. int[] arr = {1, 2, 4, 1, 2, 1, 2, 4, 5, 1, 2, 4, 5, 1, 2 ,5, 6, 7, 7, 8, 2, 1, 2, 4, 5};
  29. int pairCount = new EqualPairCounter().numberOfEqualPairsLinearithmic(arr);
  30. System.out.printf("Res: %s", pairCount); // => 49
  31. }
  32. }
Оптимальное решение, классический метод без дополнительной памяти (не считая накладных расходов на сортировку) для подсчета одинаковых пар чисел в массиве за линейно-алгорифмичное время (N* Lg N).
При этом чтобы избежать дублирования формулу подсчета комбинаций выносим в лямбду функцию(countFn).
Тестировалось на: java-11-openjdk-amd64 @ubuntu20LTS

+добавить реализацию