Medium

题目描述

给你一个二维整数数组 coordinates 和一个整数 k，其中 coordinates[i] = [xi, yi] 是二维平面中第 i 个点的坐标。

我们定义两点 (x1, y1) 和 (x2, y2) 之间的距离为 (x1 XOR x2) + (y1 XOR y2)，其中 XOR 是按位异或运算。

返回满足 i < j 且点 i 和点 j 之间的距离等于 k 的点对 (i, j) 的数量。

示例 1：

输入：coordinates = [[1,2],[4,2],[1,3],[5,2]], k = 5
输出：2
解释：我们可以选择以下点对：
- (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 <= 50000
  • 0 <= xi, yi <= 10^6
  • 0 <= k <= 100

解题思路

这道题的关键在于理解异或运算的性质和如何高效地找到满足条件的点对。

思路分析：

  1. 暴力解法：遍历所有点对，计算距离，时间复杂度 O(n²)，对于大数据会超时。

  2. 哈希表优化：利用异或运算的性质 a XOR b = c 等价于 b = a XOR c。

    对于距离公式 (x1 XOR x2) + (y1 XOR y2) = k，我们可以枚举所有可能的 x 轴异或值 dx（范围 0 到 k），那么 y 轴异或值必须是 dy = k - dx。

    对于每个点 (x1, y1)，我们需要找到满足以下条件的点 (x2, y2)：

    • x1 XOR x2 = dx → x2 = x1 XOR dx
    • y1 XOR y2 = dy → y2 = y1 XOR dy

  3. 实现策略：

    • 使用哈希表存储所有点的坐标及其出现次数
    • 对每个点，枚举所有可能的 dx 值（0 到 k）
    • 计算对应的目标点坐标，在哈希表中查找
    • 累计匹配的点对数量

这种方法的时间复杂度是 O(n × k)，由于 k ≤ 100，所以效率很高。

代码实现

class Solution {
public:
    int countPairs(vector<vector<int>>& coordinates, int k) {
        unordered_map<long long, int> count;
        
        // 统计每个坐标的出现次数
        for (auto& coord : coordinates) {
            long long key = ((long long)coord[0] << 32) | coord[1];
            count[key]++;
        }
        
        int result = 0;
        
        // 遍历每个点
        for (auto& coord : coordinates) {
            int x1 = coord[0], y1 = coord[1];
            long long key1 = ((long long)x1 << 32) | y1;
            count[key1]--; // 避免计算自己和自己的配对
            
            // 枚举所有可能的x轴异或值
            for (int dx = 0; dx <= k; dx++) {
                int dy = k - dx;
                int x2 = x1 ^ dx;
                int y2 = y1 ^ dy;
                long long key2 = ((long long)x2 << 32) | y2;
                
                if (count.find(key2) != count.end()) {
                    result += count[key2];
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def countPairs(self, coordinates: List[List[int]], k: int) -> int:
        from collections import defaultdict
        
        count = defaultdict(int)
        
        # 统计每个坐标的出现次数
        for x, y in coordinates:
            count[(x, y)] += 1
        
        result = 0
        
        # 遍历每个点
        for x1, y1 in coordinates:
            count[(x1, y1)] -= 1  # 避免计算自己和自己的配对
            
            # 枚举所有可能的x轴异或值
            for dx in range(k + 1):
                dy = k - dx
                x2 = x1 ^ dx
                y2 = y1 ^ dy
                
                if (x2, y2) in count:
                    result += count[(x2, y2)]
        
        return result

public class Solution {
    public int CountPairs(IList<IList<int>> coordinates, int k) {
        var count = new Dictionary<(int, int), int>();
        
        // 统计每个坐标的出现次数
        foreach (var coord in coordinates) {
            var key = (coord[0], coord[1]);
            if (count.ContainsKey(key)) {
                count[key]++;
            } else {
                count[key] = 1;
            }
        }
        
        int result = 0;
        
        // 遍历每个点
        foreach (var coord in coordinates) {
            int x1 = coord[0], y1 = coord[1];
            var key1 = (x1, y1);
            count[key1]--; // 避免计算自己和自己的配对
            
            // 枚举所有可能的x轴异或值
            for (int dx = 0; dx <= k; dx++) {
                int dy = k - dx;
                int x2 = x1 ^ dx;
                int y2 = y1 ^ dy;
                var key2 = (x2, y2);
                
                if (count.ContainsKey(key2)) {
                    result += count[key2];
                }
            }
        }
        
        return result;
    }
}

var countPairs = function(coordinates, k) {
    const count = new Map();
    
    // 统计每个坐标的出现次数
    for (const [x, y] of coordinates) {
        const key = `${x},${y}`;
        count.set(key, (count.get(key) || 0) + 1);
    }
    
    let result = 0;
    
    // 遍历每个点
    for (const [x1, y1] of coordinates) {
        const key1 = `${x1},${y1}`;
        count.set(key1, count.get(key1) - 1); // 避免计算自己和自己的配对
        
        // 枚举所有可能的x轴异或值
        for (let dx = 0; dx <= k; dx++) {
            const dy = k - dx;
            const x2 = x1 ^ dx;
            const y2 = y1 ^ dy;
            const key2 = `${x2},${y2}`;
            
            if (count.has(key2)) {
                result += count.get(key2);
            }
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(n × k)
空间复杂度O(n)

其中 n 是坐标点的数量，k 是给定的距离值。由于 k ≤ 100，所以实际时间复杂度接近 O(n)。