Задача: Как посчитать одинаковые пары за 1 проход (самая быстрая версия!)
Исходник: Самый быстрый подсчет одинаковых пар чисел через Хеш-таблицу, язык: java [code #802, hits: 540]
автор: this [добавлен: 04.02.2022]
  1. import java.util.HashMap;
  2. import java.util.Map;
  3.  
  4. class EqualPairCounter {
  5. int numberOfEqualPairsLinearWithExtraMap(int[] input) {
  6. int res = 0;
  7. Map<Integer, Integer> vMap = new HashMap<>();
  8.  
  9. for (final int v : input) {
  10. int count = vMap.getOrDefault(v, 0);
  11. vMap.put(v, ++count);
  12. }
  13.  
  14. for(final int v : vMap.keySet()) {
  15. if (vMap.get(v) > 1) {
  16. int pairs = vMap.get(v);
  17. res += (pairs - 1) * pairs / 2;
  18. }
  19. }
  20. return res;
  21. }
  22.  
  23. public static void main(String[] args) {
  24. int[] input = {1, 2, 4, 1, 2, 1, 2, -3, 4, 5, 1, 2, 4, 5, 1, -5, 2 ,5, 6, 7, -3, 7, 8, 2, 1, 2, -3, 4, 5};
  25. int pairCount = new EqualPairCounter().numberOfEqualPairsLinearWithExtraMap(input);
  26. System.out.println("Res: " + pairCount); // => 52
  27. }
  28. }
Данная версия быстрого алгоритма для подсчета одинаковых пар чисел в массиве за линейное время O(n) использует HashMap для хранения промежуточных результатов подсчета.
Тестировалось на: java-11-openjdk-amd64 @ubuntu20LTS

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