Вопрос интервью: обратные пары в массиве

Question

Я получил это для моего интервью: пара массивов [a, b], [b, a] считается обратной парой. например, входной массив - это [[a, b], [b, a], [a, c], [c, a], [a, b]], а выход - 2, потому что есть две обращенные пары,Теперь я могу получить временную сложность, равную O (n), используя хэш-карту, есть ли способ стать лучше, чем O (n)?

Answer 1

Алгоритм прост:

1. вы перебираете массив и подсчитываете в hashmap вхождение пар, получая результат как [ [a,b] : 2, [a,c] : 1, [b,a] : 1, ... ]
2. вы перебираетеhashmap, вычисляя минимум вхождения инвертированных пар, например, [a,b] : 2, [b,a] : 1, поэтому у вас есть 1.
3. , вы добавляете результаты из шага 2, что дает вам окончательный результат.

И вы не можете сделать это быстрее, чем O (N), потому что вы должны проверять каждый элемент хотя бы один раз.