题目描述
给你一个 二维 整数数组 coordinates
和一个整数 k
,其中 coordinates[i] = [x_i, y_i]
是第 i
个点在二维平面里的坐标。
我们定义两个点 (x1, y1)
和 (x2, y2)
的 距离 为 (x1 XOR x2) + (y1 XOR y2)
,XOR
指的是按位异或运算。
请你返回满足 i < j
且点 i
和点 j
之间距离为 k
的点对数目。
样例
输入:coordinates = [[1,2],[4,2],[1,3],[5,2]], k = 5
输出:2
解释:以下点对距离为 k:
- (0, 1):(1 XOR 4) + (2 XOR 2) = 5。
- (2, 3):(1 XOR 5) + (3 XOR 2) = 5。
输入:coordinates = [[1,3],[1,3],[1,3],[1,3],[1,3]], k = 0
输出:10
解释:任何两个点之间的距离都为 0,所以总共有 10 组点对。
限制
2 <= coordinates.length <= 50000
0 <= xi, yi <= 10^6
0 <= k <= 100
算法
(哈希表) $O(nk)$
- 将所有点存入哈希表中。
- 对于每个点,枚举其 $x$ 坐标中距离为 $i$ 的 $x’ = x \text{ XOR } i$ 坐标,并判定是否存在 $(x’, y \text{ XOR } (k - i))$ 的坐标点。
- 最终,如果 $k > 0$,则每一对点都计算了两次,返回答案除以 $2$。当 $k = 0$ 时,需要将答案减去 $n$ 后再除以 $2$。
时间复杂度
- 预处理哈希表的时间复杂度为 $O(n)$。
- 对于每个点,都需要 $O(k)$ 的时间统计答案。
- 故总时间复杂度为 $O(nk)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储哈希表。
C++ 代码
#define LL long long
class Solution {
public:
int countPairs(vector<vector<int>>& coordinates, int k) {
unordered_map<int, unordered_map<int, int>> seen;
for (const auto &c : coordinates)
++seen[c[0]][c[1]];
LL ans = 0;
for (const auto &c : coordinates) {
for (int i = 0; i <= k; i++) {
if (seen.count(c[0] ^ i) == 0)
continue;
if (seen[c[0] ^ i].count(c[1] ^ (k - i)) == 0)
continue;
ans += seen[c[0] ^ i][c[1] ^ (k - i)];
}
}
return k == 0 ? (ans - coordinates.size()) / 2 : ans / 2;
}
};