class Solution {
public:
int countPairs(vector<vector<int>>& coordinates, int k) {
}
};
6988. 统计距离为 k 的点对
给你一个 二维 整数数组 coordinates 和一个整数 k ，其中 coordinates[i] = [xi, yi] 是第 i 个点在二维平面里的坐标。
我们定义两个点 (x1, y1) 和 (x2, y2) 的 距离 为 (x1 XOR x2) + (y1 XOR y2) ，XOR 指的是按位异或运算。
请你返回满足 i < j 且点 i 和点 j之间距离为 k 的点对数目。
示例 1：
输入：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 。
示例 2：
输入：coordinates = [[1,3],[1,3],[1,3],[1,3],[1,3]], k = 0 输出：10 解释：任何两个点之间的距离都为 0 ，所以总共有 10 组点对。
提示：
2 <= coordinates.length <= 500000 <= xi, yi <= 1060 <= k <= 100原站题解
javascript 解法, 执行用时: 248 ms, 内存消耗: 53.5 MB, 提交时间: 2023-09-17 22:41:20
/**
* @param {number[][]} coordinates
* @param {number} k
* @return {number}
*/
var countPairs = function (coordinates, k) {
let ans = 0;
const cnt = new Map();
for (const [x, y] of coordinates) {
for (let i = 0; i <= k; i++) {
ans += cnt.get((x ^ i) * 2000000 + (y ^ (k - i))) ?? 0;
}
const key = x * 2000000 + y;
cnt.set(key, (cnt.get(key) ?? 0) + 1);
}
return ans;
};
golang 解法, 执行用时: 236 ms, 内存消耗: 9.9 MB, 提交时间: 2023-09-17 22:41:06
func countPairs(coordinates [][]int, k int) (ans int) {
type pair struct{ x, y int }
cnt := map[pair]int{}
for _, p := range coordinates {
x, y := p[0], p[1]
for i := 0; i <= k; i++ {
ans += cnt[pair{x ^ i, y ^ (k - i)}]
}
cnt[pair{x, y}]++
}
return
}
cpp 解法, 执行用时: 372 ms, 内存消耗: 80.9 MB, 提交时间: 2023-09-17 22:40:54
class Solution {
public:
int countPairs(vector<vector<int>> &coordinates, int k) {
int ans = 0;
unordered_map<long long, int> cnt;
for (auto &p: coordinates) {
for (int i = 0; i <= k; i++) {
// 直接 ans += cnt[...] 会插入不存在的点
auto it = cnt.find((p[0] ^ i) * 2000000LL + (p[1] ^ (k - i)));
if (it != cnt.end()) {
ans += it->second;
}
}
cnt[p[0] * 2000000LL + p[1]]++;
}
return ans;
}
};
java 解法, 执行用时: 105 ms, 内存消耗: 58.3 MB, 提交时间: 2023-09-17 22:40:40
class Solution {
public int countPairs(List<List<Integer>> coordinates, int k) {
int ans = 0;
var cnt = new HashMap<Long, Integer>();
for (var p : coordinates) {
int x = p.get(0), y = p.get(1);
for (int i = 0; i <= k; i++) {
ans += cnt.getOrDefault((x ^ i) * 2000000L + (y ^ (k - i)), 0);
}
cnt.merge(x * 2000000L + y, 1, Integer::sum);
}
return ans;
}
}
python3 解法, 执行用时: 1392 ms, 内存消耗: 26.8 MB, 提交时间: 2023-09-17 22:40:26
class Solution:
def countPairs(self, coordinates: List[List[int]], k: int) -> int:
ans = 0
cnt = Counter()
for x, y in coordinates:
for i in range(k + 1):
ans += cnt[x ^ i, y ^ (k - i)] # tuple 的括号可以省略
cnt[x, y] += 1 # tuple 的括号可以省略
return ans