arrays - 面试题：数组中的反向对

Question

我在面试时得到了这个：一对数组 [a,b],[b,a] 被算作反向对。例如输入数组是[[a,b],[b,a],[a,c],[c,a],[a,b]]，输出是2，因为有两个相反的对. 现在我可以使用哈希图将时间复杂度设为 O(n)，有什么方法可以比 O(n) 更好吗？

标签： arraysalgorithmhashmap

Answer 1

算法很简单：

1. 你遍历一个数组，并在 hashmap 中计算对的出现，得到类似的结果[ [a,b] : 2, [a,c] : 1, [b,a] : 1, ... ]
2. 您遍历哈希图，计算逆对出现的最小值，例如[a,b] : 2, [b,a] : 1，所以您有1.
3. 您添加第 2 步的结果，这将为您提供最终结果。

而且你不能比 O(N) 更快，因为你必须至少检查每个元素一次。