Задача: Как посчитать одинаковые пары за 1 проход (самая быстрая версия!)
Исходник: Один из самых быстрых способов посчитать одинаковые пар чисел за O(n), язык: java [code #801, hits: 55]
автор: this [добавлен: 29.01.2022]
  1. class EqualPairCounter {
  2. int numberOfEqualPairsLinearWithExtraArray(int[] input) {
  3. int max = input[0];
  4. int min = input[0];
  5. for (int v : input) {
  6. max = Math.max(max, v);
  7. min = Math.min(min, v);
  8. }
  9. int shift = min;
  10. int[] countArr = new int[max - min + 1];
  11. for (int v : input) {
  12. int countIdx = v - shift;
  13. countArr[countIdx]++;
  14. }
  15.  
  16. int res = 0;
  17. for(int count : countArr) {
  18. if (count > 1) {
  19. res += (count - 1) * count / 2;
  20. }
  21. }
  22.  
  23. return res;
  24. }
  25.  
  26. public static void main(String[] args) {
  27. 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};
  28. int pairCount = new EqualPairCounter().numberOfEqualPairsLinearWithExtraArray(input);
  29. System.out.println("Res: " + pairCount); // => 52
  30. }
  31. }
Самый быстрый алгоритм для подсчета одинаковых пар чисел в массиве за линейное время O(n), но конечно требует O(n) дополнительной памяти на вспомогательный массив для хранения промежуточных результатов.
Размер же этого дополнительного массива - всегда меньше либо равно длине исходной последовательности/массива, скажем так - в большинстве случаев меньше как раз засчет повторяющихся элементов.
Тестировалось на: java-11-openjdk-amd64 @ubuntu20LTS

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